Efficient Active Search for Combinatorial Optimization Problems
Authors: André Hottung, Yeong-Dae Kwon, Kevin Tierney
ICLR 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We evaluate the proposed EAS approaches on the traveling salesperson problem (TSP), the capacitated vehicle routing problem (CVRP) and the job shop scheduling problem (JSSP). In all experiments, EAS leads to significantly improved performance over sampling approaches. |
| Researcher Affiliation | Collaboration | André Hottung Bielefeld University, Germany andre.hottung@uni-bielefeld.de Yeong-Dae Kwon Samsung SDS, Korea y.d.kwon@samsung.com Kevin Tierney Bielefeld University, Germany kevin.tierney@uni-bielefeld.de |
| Pseudocode | No | The paper describes its methods using prose and mathematical equations, but it does not include any clearly labeled pseudocode or algorithm blocks. |
| Open Source Code | Yes | Our source code is available at https://github.com/ahottung/EAS. |
| Open Datasets | Yes | We use the 10,000 TSP instances with n = 100 from Kool et al. (2019) for testing and three additional sets of 1,000 instances to evaluate generalization performance. We use the 10,000 CVRP instances from Kool et al. (2019) for testing and additional sets of 1,000 instances to evaluate the generalization performance. |
| Dataset Splits | Yes | The hyperparameters λ, σ, α, and the learning rate for the optimizer are tuned via Bayesian optimization using scikit-optimize (Head et al., 2020) on separate validation instances, which are sampled from the same distribution as the test instances. We use the 10,000 TSP instances with n = 100 from Kool et al. (2019) for testing and three additional sets of 1,000 instances to evaluate generalization performance. |
| Hardware Specification | Yes | We run all experiments on a GPU cluster using a single Nvidia Tesla V100 GPU and a single core of an Intel Xeon 4114 CPU at 2.2 GHz for each experiment. |
| Software Dependencies | No | The paper mentions software like 'Adam optimizer' and 'scikit-optimize (Head et al., 2020)' but does not provide specific version numbers for these dependencies. |
| Experiment Setup | Yes | The hyperparameters λ, σ, α, and the learning rate for the optimizer are tuned via Bayesian optimization using scikit-optimize (Head et al., 2020) on separate validation instances, which are sampled from the same distribution as the test instances. For greedy action selection, POMO generates 8 n solutions for an instance of size n (using 8 augmentations and n different starting cities). In all other cases, we generate 200 8 n solutions per instance (over the course of 200 iterations for the (E)AS approaches). The batch size (the number of instances solved in parallel) is selected for each method individually to fully utilize the available GPU memory. |