Simulation-guided Beam Search for Neural Combinatorial Optimization
Authors: Jinho Choo, Yeong-Dae Kwon, Jihoon Kim, Jeongwoo Jae, André Hottung, Kevin Tierney, Youngjune Gwon
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We evaluate our methods on well-known CO benchmarks and show that SGBS significantly improves the quality of the solutions found under reasonable runtime assumptions. We show the effectiveness both of SGBS and the SGBS+EAS hybrid on a standard benchmark of the traveling salesperson problem (TSP), capacitated vehicle routing problem (CVRP), and the flexible flow shop problem (FFSP). |
| Researcher Affiliation | Collaboration | Jinho Choo 1 Yeong-Dae Kwon 1 Jihoon Kim1 Jeongwoo Jae1 Andr e Hottung2 Kevin Tierney2 Youngjune Gwon1 1Samsung SDS, Korea 2Bielefeld University, Germany |
| Pseudocode | Yes | Algorithm 1 Simulation-guided Beam Search (SGBS) |
| Open Source Code | Yes | Our code for the experiments described in the paper is publicly available at https://github.com/ yd-kwon/SGBS. |
| Open Datasets | Yes | For our experiments, we use n = 100 with 10,000 instances from Kool et al. [4]. |
| Dataset Splits | No | The paper states that models were 'pre-trained by the POMO [14] RL technique' and uses 'n = 100 with 10,000 instances' and 'n = 150, 200 test sets of 1,000 instances' for evaluation, but does not explicitly provide the specific train/validation/test splits used for the training process itself. |
| Hardware Specification | Yes | Our experiments are carried out on A100 GPUs (Nvidia) with 80 GB memory. |
| Software Dependencies | Yes | Results of our SGBS experiments and the ablation studies are summarized in Table 2 along with the results [13] by CPLEX [51] with mixed-integer programming models and meta-heuristic solvers. |
| Experiment Setup | Yes | SGBS hyperparameters are set to (β, γ) = (10, 10) and (4, 4) for the TSP and CVRP, respectively. |