BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization
Authors: Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, Jean-Marc Andreoli
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We illustrate our approach on five classical problems: the Euclidean and Asymmetric Traveling Salesman, Capacitated Vehicle Routing, Orienteering and Knapsack Problems. Furthermore, for each problem, we introduce a simple attention-based policy network for the BQMDPs, which we train by imitation of (near) optimal solutions of small instances from a single distribution. We obtain new state-of-the-art results for the five COPs on both synthetic and realistic benchmarks. Notably, in contrast to most existing neural approaches, our learned policies show excellent generalization performance to much larger instances than seen during training, without any additional search procedure. Our code is available at: url. |
| Researcher Affiliation | Collaboration | Darko Drakulic, Sofia Michel, Florian Mai , Arnaud Sors, Jean-Marc Andreoli Naver Labs Europe firstname.lastname@naverlabs.com IDIAP Research Institute, Work done during an internship at Naver Labs Europe |
| Pseudocode | No | No explicit pseudocode or algorithm blocks were found. |
| Open Source Code | Yes | Our code is available at: url. |
| Open Datasets | Yes | For all routing problems, we train our model and all baselines on synthetic instances of size 100, following the same procedure of data generation as in [28]. For asymmetric TSP, we use Euclidean distance matrices and randomly break symmetries. ... we test the trained models on synthetic instances of size 100, 200, 500 and 1K generated from the same distribution, as well as the standard TSPLib and CVRPLib datasets. ... Solutions of these problems are obtained by using the Concorde solver [1] for TSP, LKH heuristic [17] for ATSP and CVRP, and EA4OP heuristic [26] for OP. We use a dataset of 1 million solutions. |
| Dataset Splits | No | The paper describes training on '1 million solutions' for 'relatively small and fixed size' instances and testing on 'synthetic instances of size 100, 200, 500 and 1K' and 'standard TSPLib and CVRPLib datasets'. However, it does not explicitly specify a validation set or numerical splits (e.g., percentages or exact counts) for training, validation, and test sets. It only mentions different sizes for training and testing data. |
| Hardware Specification | Yes | In our experiments, we run all deep learning models on a single Nvidia Tesla V100-S GPU with 24GB memory, and other solvers on Intel(R) Xeon(R) CPU E5-2670 with 256GB memory, in one thread. |
| Software Dependencies | No | The paper mentions Concorde solver [1], LKH heuristic [17], EA4OP heuristic [26], and Adam [25] optimizer, but it does not specify version numbers for these or other software components like deep learning frameworks (e.g., PyTorch, TensorFlow) or Python. |
| Experiment Setup | Yes | The model has 9 layers, each built with 12 attention heads with embedding size of 192 and dimension of feed-forward layer of 512. Batches of size 1024 are formed, and the model is trained for 500 epochs. We use Adam [25] as optimizer with an initial learning rate of 7.5e-4 and decay of 0.98 every 50 epochs. |