Large Neighborhood Search with Decision Diagrams
Authors: Xavier Gillard, Pierre Schaus
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In order to evaluate the effectiveness of DD-LNS, we considered two sequencing problems: a discrete lot sizing and scheduling problem (DSLP) and the traveling salesman problem with time windows (TSPTW). All our experiments were performed on the same physical machine... Table 1 shows the number of DLSP instances for which the best solution found by each solver matches the best known solution. |
| Researcher Affiliation | Academia | Xavier Gillard , Pierre Schaus Universit e Catholique de Louvain, BELGIUM {xavier.gillard, pierre.schaus}@uclouvain.be |
| Pseudocode | Yes | Algorithm 1 Top Down Compilation of an Exact DD, Algorithm 2 Top Down Compilation of a Restricted DD, Algorithm 3 LNS with Decision Diagrams, Algorithm 4 Restrict Procedure |
| Open Source Code | Yes | All source code and data are freely available online at: https://github.com/xgillard/ijcai 22 DDLNS. Contact Author |
| Open Datasets | Yes | All source code and data are freely available online at: https://github.com/xgillard/ijcai 22 DDLNS. Contact Author. Our experiments cover the 467 instances of the benchmark suites which are usually used to assess the efficiency of new TSPTW solvers. |
| Dataset Splits | No | The paper mentions using 500 generated instances for DSLP and 467 instances from benchmark suites for TSPTW, but does not provide specific details on train/validation/test splits, percentages, or methodology for creating such splits. |
| Hardware Specification | Yes | All our experiments were performed on the same physical machine equipped with two Intel(R) Xeon(R) CPU E52687W v3 and 128Gb of RAM. |
| Software Dependencies | Yes | All MIP models originate from [Pochet and Wolsey, 2006] and are written using FICO Xpress Mosel v8.11. We compared the performance of DD-LNS against an implementation of the CP model from section 6.2 in Choco 4.10.6. |
| Experiment Setup | Yes | On that machine, each considered solver was given a 10 minutes timespan using a single thread and a maximum memory quota of 2Gb in order to solve each instance. using a LNS that re-optimizes a small sequence4 of 5 decision variables xi . . . xi+4 randomly selected at each restart. |