PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization
Authors: André Hottung, Mridul Mahajan, Kevin Tierney
ICLR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We evaluate Poly Net on four combinatorial optimization problems and observe that the implicit diversity mechanism allows Poly Net to find better solutions than approaches that explicitly enforce diverse solution generation. We assess Poly Net s performance across four problems: the TSP, the CVRP, CVRPTW, and the flexible flow shop problem (FFSP). |
| Researcher Affiliation | Academia | André Hottung Bielefeld University, Germany EMAIL; Mridul Mahajan Boston University, USA EMAIL; Kevin Tierney Bielefeld University, Germany EMAIL |
| Pseudocode | No | The paper describes the Poly Net architecture, training, and experimental setup in detail, but it does not include any explicit pseudocode blocks or algorithms formatted as such. |
| Open Source Code | Yes | Our implementation of Poly Net is available at https://github.com/ ahottung/Poly Net. Furthermore, Poly Net is also implemented in the RL4CO framework (Berto et al., 2024a). |
| Open Datasets | Yes | To generate problem instances, we adhere to the methodology outlined in Kool et al. (2019). We use the CVRP instance generator outlined in Queiroga et al. (2022) to generate customer positions and demands, and we adhere to the methodology established in Solomon (1987) for generating the time windows. We generate problem instances randomly according to the method in Kwon et al. (2021). |
| Dataset Splits | Yes | For the considered routing problems, we train separate models for problem instances of size 100 and 200, and then evaluate the models trained on n = 100 using instances with 100 and 150 nodes, and the models trained on n = 200 using instances with 200 and 300 nodes. We use the 10,000 test instances with n = 100 from Kool et al. (2019) and test sets consisting of 1,000 instances from Hottung et al. (2021) for n = 150 and n = 200. We generate different instance sets for training, validation, and testing. |
| Hardware Specification | Yes | Our experiments are conducted on a GPU cluster utilizing a single Nvidia A100 GPU per run. |
| Software Dependencies | No | The paper mentions baselines like Py VRP (Version 0.5.0) and CPLEX (CPLEX-Optimization-Studio, 2020), and that Poly Net is implemented in the RL4CO framework, but it does not specify version numbers for general software dependencies like Python or PyTorch, which would be necessary for full reproducibility of the authors' own implementation. |
| Experiment Setup | Yes | For the training of Poly Net models, we set the parameter K to 128 across all problems. We use a learning rate of 10 4 for the TSP and CVRP and 10 5 for the CVRPTW. For instances of size n=100, we train our models for 300 epochs (200 for the TSP), with each epoch comprising 4 108 solution rollouts. To optimize GPU memory utilization, we adjust the batch size separately for each problem and its dimensions. In all experiments, the new Poly Net layers comprise two linear layers, each with a dimensionality of 256. |