Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Improved Peel-and-Bound: Methods for Generating Dual Bounds with Multivalued Decision Diagrams
Authors: Isaac Rudich, Quentin Cappart, Louis-Martin Rousseau
JAIR 2023 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We tested the method on the sequence ordering problem, and our results indicate that our peel-and-bound scheme generates stronger bounds than a branch-and-bound scheme using the same propagators, and at significantly less computational cost. In this extended version of the paper, we also propose new methods for using relaxed decision diagrams to improve the solutions found using restricted decision diagrams, discuss the heuristic decisions involved with the parallelization of peel-and-bound, and discuss how peel-and-bound can be hyperoptimized for sequencing problems. Furthermore, we test the new methods on the sequence ordering problem and the traveling salesman problem with time-windows (TSPTW), and include an updated and generalized implementation of the algorithm capable of handling any discrete optimization problem. The new results show that peel-and-bound outperforms ddo (a decision diagram based branch-and-bound solver) on the TSPTW. We also close 15 open benchmark instances of the TSPTW. The original computational experiments are proposed and discussed in Section 4. The new computational experiments and improved implementation of the algorithm are discussed in Section 5. |
| Researcher Affiliation | Academia | Isaac Rudich EMAIL Quentin Cappart EMAIL Louis-Martin Rousseau EMAIL 2500 Chem. de Polytechnique, Montr eal, QC H3T 1J4, Canada |
| Pseudocode | Yes | Algorithm 1: Refining Decision Diagrams for Sequencing (Cire & van Hoeve, 2013) Algorithm 2: Decision Diagram based Branch-and-Bound (Bn B) (Bergman et al., 2016b) Algorithm 3: Peel-and-Bound (Pn B) Algorithm Algorithm 4: Peeling process used in Algorithm 3 |
| Open Source Code | Yes | 1. https://github.com/Isaac Rudich/Improved Pn B |
| Open Datasets | Yes | The solver was tested using DD widths of 64, 128, and 256 on the 41 SOP problems available in TSPLIB (Reinelt, 1991). For comparisons between Pn B and Bn B, a timestamp, new bounds, and the length of the remaining queue were recorded each time the bounds on a problem were improved. [...] We test our solver on the same set of 467 benchmark instances used by Gillard et al. (2021) to test their implementation of decision diagram based branch-and-bound (ddo). These instances are available from L opez-Ib a nez & Blum (2022), and include the following sets: AFG (Ascheuer, 1996), Dumas (Dumas et al., 1995), Gendreau Dumas (Gendreau et al., 1998), Langevin (Langevin et al., 1993), Ohlmann-Thomas (Ohlmann & Thomas, 2007), Solomon-Pesant (Pesant et al., 1998), and Solomon-Potvin-Bengio (Potvin & Bengio, 1996). |
| Dataset Splits | No | The paper uses well-known benchmark instances (SOP from TSPLIB and TSPTW from López-Ibáñez & Blum) as problem sets for evaluation. These are treated as individual problem instances to be solved, rather than a dataset to be split into training, validation, and test sets for model development. No explicit dataset splits (percentages, counts, or specific files) are provided within the paper for these benchmark instances. |
| Hardware Specification | Yes | The experiments were performed on a computer equipped with an AMD Rome 7532 at 2.40 GHz with 186Gb RAM. |
| Software Dependencies | No | Both algorithms are implemented in Julia and are open-source3. To ensure a fair comparison, both algorithms resort to the same function for generating relaxed decision diagrams (Algorithm 1), and the same function for generating restricted decision diagrams. [...] We have since re-implemented peel-and-bound so the implementation is generic. |
| Experiment Setup | Yes | The solver was tested using DD widths of 64, 128, and 256 on the 41 SOP problems available in TSPLIB (Reinelt, 1991). [...] Execution time was limited to 3,600 seconds. [...] All of the new tests were performed using 2048 as the maximum width, and included a diversified search with k = 5 using the procedure described in Section 3.2.5. [...] Since the solution space of TSPTW tends to be drastically more constrained than SOP, at least for the benchmark instances, it is more difficult to find feasible solutions, and we use a width of 100 for the initial diversified search. [...] The experiments were limited to 3600 seconds. |