PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization
Authors: André Hottung
Mridul Mahajan
Kevin Tierney
Venue: ICLR 2025 Poster (2025)
Keywords: neural combinatorial optimization
learning to optimize
reinforcement learning
routing problems
Primary area: reinforcement learning
TL;DR: A novel approach for neural combinatorial optimization that uses a single-decoder model to learn multiple complementary solution strategies.

Abstract: Reinforcement learning-based methods for constructing solutions to combinatorial optimization problems are rapidly approaching the performance of human-designed algorithms. To further narrow the gap, learning-based approaches must efficiently explore the solution space during the search process. Recent approaches artificially increase exploration by enforcing diverse solution generation through handcrafted rules, however, these rules can impair solution quality and are difficult to design for more complex problems.  In this paper, we introduce PolyNet, an approach for improving exploration of the solution space by learning complementary solution strategies. In contrast to other works, PolyNet uses only a single-decoder and a training schema that does not enforce diverse solution generation through handcrafted rules. We evaluate PolyNet on four combinatorial optimization problems and observe that the implicit diversity mechanism allows PolyNet to find better solutions than approaches that explicitly enforce diverse solution generation.

Published as a conference paper at ICLR 2025
POLYNET: LEARNING DIVERSE SOLUTION STRATE- GIES FOR NEURAL COMBINATORIAL OPTIMIZATION
André Hottung
Mridul Mahajan Boston University, USA mr i du 1m@bu. edu
Bielefeld University, Germany
andre. www.hunguunu www.::uuunndbeeeeeeeeeeed.e..ede
Kevin Tierney
Bielefeld University, Germany kevin. tierney@uni -ttee//unnndeeeeeeddddd.
ABSTRACT
Reinforcement learning-baser methods for constructing solutions to combinatorial optimization problems are rapidly approaching the performance of human- designd algorithms. To further narrow the gap, learning-based approaches must efficiently explore the solution space during the search process. Recent approaches artificially increase exploration by enforcing diverse solution generation through handcrafted rules, however, these rules can impair solution quality and are difficult to design for more complex problems. In this paper. we introduce PolyNet, approach for improving exploration of the solution space by learning complementary solution strategies. In contrast other works, PolyNet uses only a single-decoder and training schema that does not enforce diverse solution generation through hand- crafted rules. We evaluate PolyNet on four combinatorial optimization problems and observe that the implicit diversity mechanism allows PolyNet to find better solutions than approaches that explicitly enforce diverse solution generation.
INTRODUCTION
There have been remarkable advancements in recent years in the field of learning- based approaches for solving combinatorial optimization (CO) problems (Bello et al. al.] 2016; Kool al., 2019. Kwon et al.) 2020). Notably, reinforcement learning (RL) methods have emerged that build a solution to a problem step-by-step in a sequential decision making process. Initially, these construction techniques struggled to produce high-quality solutions. However, recent methods have surpassed even established operations research heuristics, such as LKH3, for simpler, smaller-scale routing problems. Learning-base approaches thus now have the potential to become versatile tools, capable of learning specialized heuristics tailored to unique business-specift, problems. Moreover, with access sufficiently large training datasets, they may consistently outperform off-the-shelf solvers in numerous scenarios. This work aims to tackle some of the remaining challenges that currently impede the widespread adoption of Icarning-basee heuristic methods in practical applications.
A key limitation of learning-based approaches is that they struggle to sufficiently explore the solution space. The metaheuristies literature identifies exploration as key component of heuristic optimization procedures (Blum & Roli 2003), but examining diverse solutions alone is not enough to find high- quality solutions. Mahfoud (1995) discuss the need for useful diversity, i.e., diversity that "helps in achieving some purpose goal." To encourage search diversity, many recent neural construction methods (e-g.. Li et al. (2023a); Choo et al. (2022)) follow the POMO approach (K won al. 2020) and improve exploration by forcing diverse first actions during solution construction. While this creates significant diversity through exploiting symmetrics in the problem representation (every solution has different first action), effort is made to encourage diversity subsequent the first action. Furthermore, in more complex optimization problems the initial action can significantly influence the solution quality, rendering these methods less effective at generating solutions.
Acknowledging that useful diversity is an essential component of search techniques, neural CO approaches have begun attempting to encourage more exploration during search. Xin et al. 2021)

---

Published as a conference paper at ICLR 2025
propose transformer model with multiple decoders that encourage each decoder to learn distinct solution strategy during training by maximizing the Kullback-Leibler (KL) divergence between decoder output probabilities. However, to manage computational costs, diversity is only promoted in the initial construction step. In contrast, (Grinsstaa et al. (2023) introduce Poppy. a training procedure for multi-decoder models that increases diversity without relying KI. divergence. Poppy generates a population (i.e., a set) of decoders during the learning phase by training only the best-performing decoder for each problem instance. While effective, Poppy is computationally intensive, requiring a separate decoder for each policy, thus limiting the number of learnable policies per problem.
In this paper, we introduce PolyNet to address the previously discussed limitations:
1. PolyNet learns diverse and complementary of solution strategies for improved explo- ration using a single decoder.
2. PolyNet increases exploration without enforcing the first construction action, allowing its applicability to a wider range of CO problems
By utilizing a single decoder to learn multiple strategies, PolyNet quickly generates a set of diverse solutions for problem instance. This significantly enhances exploration, allowing to find better solution during training and testing. Furthermore, by abandoning the concept of forcing diverse first actions, exclusively rely on PolyNet's inherent diversity mechanism to facilitate exploration during the search. This fundamental change improves solution generation for problems in which the first move greatly influences performance, such in the CVRP with time windows (CVRPTW).
PolyNet is an autoregressive construction method, which makes a direct application to large-scale routing problems computationalyy impractical. However, small- and medium-scal routing problems, which often involve numerous constraints (e.g., customer time windows), are frequently encountered in practice. This reflected in the current focus of the operations research community, which prioritizes smaller problems with numerous complex constraints (c.g.. Zha.g et al. (2024); Cataldo Diaz al. (2024); Lera-Romero et al. 2024); Jolfaei & Alinaghian (2024). With PolyNet, we aim to take step toward addressing these more complex problems by enabling diverse solution generation without relying on the symmetries characteristic of simpler routing problems.
We assess PolyNet's performance across four problems: the TSP, the CVRP, CVRPTW, and the flexible flow shop problem (FFSP). Across all problems, PolyNet consistently demonstrates a significant advancement over the state-of-the-arr.. Moreover, we observe that the solution diversity arising during PolyNet's training enables the discovery of superior solutions compared to artificially enforcing diversity by fixing the initial solution construction step.
LITERATURE REVIEW
Neural CO In their seminal work, Vinyals et al. (2015) introduce the pointer network architecture, an early application of modern machine learning methods to solve CO problems. Pointer networks autoregressively generate discrete outputs corresponding to input positions. When trained via supervised learning, they can produce solutions for the TSP with up to 50 nodes. Bello al.) (2016) propose training pointer networks using reinforcement learning instead and illustrate the efficacy of this method in solving larger TSP instances. However, these early methods are limited in generalization and in the quality of the generated solutions.
Nazari et al. (018)) extend the pointer network architecture address the CVRP with up to 100 nodes. Building on this, Kool et al. (2019) enhance the architecture by introducing a transformer- based encoder with celf-attention Vaswani et al.) (207)), enabling the model learn more effective policies and produce higher-qualin solutions. Recognizing that many CO problems exhibit inherent symmetries, wwon et al. (2020) propose POMO, method that exploits these symmetries to generate diverse solutions. However, POMO's effectiveness is heavily dependent on the assumption that such symmetries can be efficiently leveraged, which limits its applicability to simple problems. Kim et al. (2022) extend these ideas and propose general- purpose symmetric learning scheme. Drakulic et al. (2023) use bisimulation quotienting (Givan et al. (2033) to improve -itt-f-diitributiinn generalization of neural CO methods. However, they use imitation learning which requires large training set of high-quality solutions limiting the applicability of their method. [uo et al. (2023) improves generalization in neural CO by using "heavy" decoder make more effective node selections
2

---

Published as a conference paper at ICLR 2025
during solution construction, but this increases computational overhead. Despite these advancements, only a few works, such as Falkner & Schmidt- Thiemee (2020). Kool et al. (2022a), Hua et al. (2025). and [Berto et al. (2024b), target routing problems with additional constraints like time windows, highlighting a gap in extending neural CO approaches to more complex problem variants.
Instead of constructing solutions autoregressively. some methods predict a heat-map that emphasizes promising solution components (e.g., arcs in a graph) and is subsequently used in a post-hoc search for solution construction (Joshi et al., 2019 Fu et al., 2021; Kool et al., 2022b) Min al. (023).
However, Xia et al. (2024) reveal that these methods often underperform compared to simpler baselines. Another class of methods iteratively improves initial solutions. [Hottung & Tierney (2020),
Ma et al. (202T), (hen & Tian (2019), and Hottung et al. (2025) iteratively improve an initial solution by performing local adjustments. Similarly, several works guide the k-opt heuristic for vehicle routing problems (Wu et al., 2019 da Costa et al.) 2020, Ma et al., 2023). These improvement methods require longer runtimes be effective. In contrast, PolyNet also excels at generating high-quality solutions quickly. [Sun& & Yang (2023) cast CO problems
discrete binary vector optimization problems and utilize denoising diffusion models for solution generation Kim et al. (2024) utilize the solution symmetry in the combinatorial space to improve the sample efficiency during training. Both approaches fail to generalize to problems with more complex constraints like the CVRPTW.
Hottung al. (2022) introduce efficient active search (EAS), method that guides the search by updating a subset of the policy parameters during inference. Choo et al. (2022) propose SGBS, an inference mechanism that combines Monte-Carlo tree search with beam search to provide search guidance. When used in combination with EAS, it achieves state-of-thee problems. [i et al. (2023b) learn a distribution of high-quality solutions using diffusion models and perform a gradient- being able to even tackle problems with more complex constraints.
performance on several
search at test time. PolyNet outperforms these recent approaches while
Diversity in metaheuristics In the context of metaheuristics, solution diversity plays crucial role in balancing the exploration-exploittiio trade-off. Population- algorithms, such as genetic algorithms, aim to maintain a pool of diverse solutions to promote thorough exploration of the search space (Gendreau et al. (01O). Additionally, some works specifically target generating multiple solutions for single-objective problems. For instance, |Hanaka et al. (2022) introduce polynomial- time algorithm to compute multiple diverse shortest paths in weighted directed graphs. Similarly, Huang et al. (219) propose a niching memetic algorithm designed to identify multiple optimal solutions for TSP instances, emphasizing diversity within the solution set.
Diversity mechanisms in RL Diversity mechanisms in RL aim to encourage exploration by generat- ing a range of strategies or solutions. Skill-learning algorithms, such as those by EEsenbach et al. (2018) and Sharma al. (2019), aim learn policies with diverse behaviors to accelerate training. However, these methods are not directly applicable to CO tasks, where diversity must also consider the quality of solutions, not just behavioral variation.
In contrast to implicitly maintaining a collection of agents through context, population-based RL techniques explicitly maintain finite agent population and use diversity mechanisms discover diverse strategies for solving RL tasks, c.g., ZZhag et al. (2019), Pierrot & Flajolet (2023), Wu et al. (2023). In neural program synthesis, [uncel al. (2018) optimize the expected reward when sampling pool of solutions and keep the best one. [i et al. (2021) I) use the mutual information between agents' identities and trajectories as an intrinsic reward to promote diversity and thus solve cooperative tasks requiring diverse strategies.
Diversity mechanisms in neural CO Kim et al. (202T) present a hierarchical strategy for solving routing problems, where a base policy learns to generate diverse candidate solutions through entropy regularization. While entropy regularization can be used to increase diversity during solution sampling, it does not allow to learn truly different strategies. Xin et al. (2021) encourage diverse solutions using multiple decoders and KL divergence regularization, while Grinsztajn et al. (2023) use agent population through multiple decoders to learn complementary strategies, updating exclusively the best tesst-erforming agent at each iteration similar to Bunel et al. (2018). While using multiple-decoders encourages diversity, it results in a large computational overhead. [Hottung et al.) (202T) and Chalumeeu et al. (2023) learn a continuous latent space that encodes solutions for CO problems and use to sample diverse solutions test time. Both approaches are designed for longer runtimes and can not be casily applied to more difficult optimization problems.
3

---

Published as a conference paper at ICLR 2025
0
000
Insttance
Embedding
Decoder
Decoder
Decoder
Euoodet
Solations
Figure 1: PolyNet solution generation.
POLYNET
3.1 BACKGROUND
Neural CO approaches seek to train neural network denoted as wy with learnable weights A. The network's purpose is to generate solution when provided with an instance To achieve this, we employ RL techniques and model the problem as a Markov decision process (MDP), wherein solution is sequentially constructed in 7 discrete time steps. At each step / E (1...., T), an action a, is selected based on the probability distribution (a (ss) defined by the neural network where is the current state. The initial state 31 encapsulates the information about the problem instance while subsequent states St+1 are derived by applying the action a, to the previous state 8ç. A (partial) solution denoted as is defined by the sequence of selected actions (01, 42, ........ . az). Once a complete solution т = Tr satisfying all problem constraints is constructed, we can compute its associated reward R(T, I). The overall probability of generating solution for an instance is defined as ( = I (e(a st).
3.2 OVERVIEW
PolyNet is a learning- -ased approach designed to learn set of diverse solution strategies for CO problems. During training, each strategy allowed to specialize a subset of the training data. This essentially results in a portfolio of strategies, which are known to be highly effective for solving CO problems (Bischl al. (016). Our pursuit of diversity is fundamentally means enhance exploration and consequently solution quality. Note that PolyNet not only enhances performance at test time (where sample multiple solutions for each strategy and keep only the best one), but also improves exploration during training.
PolyNet aims learn K different solution strategies T...--. * using single neural network. To achieve this, we condition the solution generation process on an additional input E {UI,..., UK} that defines which of the strategies should be used to sample solution so that
11 TK = TT( (1,))..... ... Te(TK FK).
We use of unique bit vectors for {ui...., .,, UK J. Alternative representations should also be feasible as long as they are easily distinguishable by the network.
PolyNet uses a neural network that builds on the established transformer architecture for neural CO (Kool et al. 2019). The model consists of an encoder that creates an embedding of a problem instance, and decoder that generates multiple solutions for an instance based on the embedding. To generate solutions quickly, we only insert the bit vector into the decoder, allowing us generate multiple diverse solutions for an instance with only a single pass through the computationally expensive encoder. [Toows the overall solution generation process of the model where bit vectors of size 4 are used to generate to generate 16 different solutions for a CVRP instance.
3.3 TRAINING
During training we (repeatedly) sample K solutions {fI...., Tx} for an instance / based on K different vectors {UI,.... ux }, where the solution is sampled from the probability distribution TT(T, v;). To allow the network to learn K different solution strategies, we follow the Poppy method (Grinsztajn et al. 2023) and only update the model weights with respect to the best of the
4

---

Published as a conference paper at ICLR 2025
K' solutions. Let r' be the best solution, i.e., T" arg e e(n.....kk R( [), and let v" be the corresponding vector (ties are broken arbitrarily). We then update the model using the gradient
v RE- [ .1) V.VVo log"o(r" [,,""]}
where b, a baseline (which we discuss in detail below). Updating the model weights only based on the best found solution allows the network to learn specialized strategies that do not have to work well on all instances from the training set. While this approach does not explicitly enforce diversity, incentivizes the model to learn diverse strategies in order to optimize overall performance. For more in depth discussion on how this loss leads to diverse solution generation, see Grinsztajn et al. (2023).
Exploration & baseline Many recent neural construction heuristics follow the POMO approach and rollout V solutions from N different starting states per instance to increase exploration. This is possible because many CO problems contain symmetries in the solution space that allow optimal solution to be found from different states. In practice, this mechanism is implemented by forcing a different first construction action for each of the N rollouts. Forcing diverse rollouts significantly improves exploration. However, this exploration mechanism should not be used when the first action can not be freely chosen without impacting the solution quality.
In PolyNet, we do not use an exploration mechanism that assumes symmetries in the solution space during training. Instead, we only rely on the exploration provided by conditional solution generation. This allows us to solve a wider range of optimization problems. As a baseline we simply use the average reward of all K rollouts for an instance, i.e., bo K Σ R(T:.)).
3.4 NETWORK ARCHITECTURE
PolyNet extends the neural network architecture of the POMO approach by new residual block in the decoder. This design allows us to start PolyNet's training from already trained POMO model, which significantly reduces the amount of training time needed. Figure shows the overall architecture of the modified decoder including the new PolyNet lay- ers. The new layers accept the bit vector as input and use it to calculate an update for the output of the masked multi-head attention mechanism. They consist of concatenation operation followed by two linear layers with a ReLU activation function in be- tween. See Kwon et al. (2020) for more details on the encoder and decoder.
Node Embeddings
Contest Embeeding
+
Bss Vector
Linrat
Linaat
Misiol Multi-Head Attention
Conent
Poigite Loyers
ReLUU
Mechonism
Lincor
Ourput
Figure 2:
Decoder architecture
The output of the new layers directly impacts the pointer mechanism used to calculate the output probabilities, allowing the new layers to significantly influence the solution generation based on v. However, the model can also learn to completely ignore by setting all weights of the second linear layer to zero. This is intentional, as our objective is to increase diversity via the loss function, rather than force unproductive diversity through the network architecture.
3.5 SEARCH
A simple and fast search procedure given an unseen test instance is to sample multiple solutions in parallel and return the best one. Specifically, construct a of M distinct solutions, we initially draw M binary vectors from the set t...... Uk. allowing for replacement if M exceeds the size of K. Subsequently, we employ each of these M vectors to sample individual solutions. This approach generates diverse set of instances in parallel and independent manner, making it particularly suitable for real-world decision support settings where little time is available.
To facilitate more extensive, guided search, PolyNet can be combined with EAS. EAS is simple technique to fine-tune a subset of model parameters for a single instance in an iterative process driven by gradient descent. In contrast to the EAS variants described in Hottung et al. (202)). we do not insert any new layers into the network or update the instance embeddings. Instead, we only fine- tune the new PolyNet layers during search. Since PolyNet is specifically trained to create diverse solutions
5

---

Published as a conference paper at ICLR 2025
based these layers, EAS can easily explore wide variety of solutions while modifying only subset of the model parameters.
EXPERIMENTS
We compare PolyNet's search performance to state-of-the-art methods on four established problems. We also explore solution diversity during the training and testing phases and analyze the impact of the free first move selection. An ablation study for our network architecture changes is provided in Appendix B While most of our evaluation focused on routing problems, we demonstrate that PolyNet can also be used to solve other CO problems by applying PolyNet to the FFSP (see Appendix A). Our experiments are conducted on a GPU cluster utilizing a single Nvidia A GPU per run. In all experiments, the new PolyNet layers comprise two linear layers, each with dimensionality of 256. Our implementation of PolyNet available at whtttps:/ htapps://qithie qightbhhhhug.. com/ Furthermore, PolyNet is also implemented in the RL4CO framework (Berto
shottung/Polyyg et al. 2024a).
4.1 PROBLEMS
TSP The TSP is thoroughly researched routing problem which the goal is to find the shortest tour among set of nodes. The tour must visit each node exactly once and then return to the initial starting node. We consider the TSP due to its significant attention from the machine learning (ML) community, making it well-established benchmark for ML-based optimization approaches. However, is important to note that instances with n S 300 can be quickly solved to optimality by CO solvers that have been available for many years. To generate problem instances, adhere the methodology outlined in Kool et al. (2019).
The objective of the CVRP is determine the shortest routes for fleet of vehicles tasked with delivering goods to a set of n customers. These vehicles start and conclude their routes at a depot and have a limited capacity of goods that they can carry. CVRP instances are considerably more difficult to solve than TSP instances of equivalent size (despite both problems being of the same computational complexity class). Even cutting-edee edge CO methods struggle reliably find optimal solutions for instances with < 300 customers. To generate problem instances, we again adopt the approach outlined in Kool et al. (2019).
CVRP
CVRPTW The CVRPTW is an extension of the CVRP that introduces temporal constraints limiting when a customer can receive deliveries from a vehicle. Each customer is associated with a time window, comprising arrive early a customer i, but they must wait until the specified earliest arrival time e, before making delivery. The travel duration between customer i and customer is calculated as the Euclidean distance between their locations, and each delivery has a fixed duration. All vehicles initiate their routes from the depot at time 0. We the CVRP instance generator outlined in Queiroga al. (2022) to generate customer positions and demands, and we adhere to the methodology established in Solomon 1987 for generating the time windows. It's essential to note that customer positions not sampled from uniform distribution; instead, they are clustered to replicate real-world scenarios. Further details for instance generation are given in Appendix
earliest arrival time and a latest allowable arrival time 4. Vehicles may
FFSP
The description of the FFSP and all experimental results can be found Appendix A
4.2 SEARCH PERFORMANCE
We conduct an extensive evaluation of PolyNet's search performance, benchmarking against state- of-the-art methods. 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= n= 100 using instances with 100 and 150 nodes, and the models trained on = 200 using instances with 200 and 300 nodes. We can thus assess the model's 's capability to generalize to instances that diverge from the training data. Throughout evaluation, employ the instance augmentation technique of K Kwon al. (2020).

---

Published as a conference paper at ICLR 2025
Table 1: Search performance results for TSP.
Test (10K instances)
Test (LK instances)
Generalization
(1K instances)
Method
rite
Theoo 100
Navol = 200
ne-
100.
Denat
150
fite =200,
300
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
Concorde
7.765
82m
10.687
31m
9.346
17m
12.949
83m
LKH3
7.765
0.000%
8h
10.687
0.000%
3h 9.346
0.000%
99m
12.949
0.000%
5h
Unguided
POMO gready
7.775
0.135%
Im 10.770
0.780%
<Im 9.393
0.494%
<Im 13.216
2.061%
1m
sampling
7.772
0.100%
3m
10.759
0.674%
2m 9.385
0.411%
Im
13.257
2.378%
7m
Poppy
7.766
0.015%
4m
10.711
0.226%
2m 9.362
0.164%
Im
13.052
0.793%
7m
PolyNet
I| 7.765
0.000%
4m 10.690
0.032% %
2m
9.352
0.055
1m 12.995
0.351 %
8m
DPDP
7.765
0.004%
2h
9.434
0.937%
44m
COMPASS
7.765
0.002%
2h
9.354
0.083%
32m
Guided
MDAM
7.781
0.208%
4h
9.403
0.603%
1h
POMO
EAS
7.769
0.053
3h 10.720
0.310%
3h
9.363
0.172%
1h
13.048
0.761%
8h
SGBS
7.769
0.058%
9m 10.727
0.380%
24m
9.367
0.220%
8m
13.073
0.951% %
77m
SGBS+EAS
7.767
0.035%
3h 10.719
0.300%
3h
9.359
0.136%
1h 13,050
0.776%
PolyNet EAS || 7.765
0.000%
3h 10.687
0.001 %
2h
9.347
0.001 %
1h
12.952
0.018%
For the training of PolyNet models, we set the parameter K 128 across all problems. We use learning rate of 10-4 for the TSP and CVRP and 10-3 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 x 10 solution rollouts. Note that we warm-start the training for these models using previously trained POMO models to reduce training times (results for cold-starting training can be found Appendix ( For instances with n==000, we start training based on the = 100 PolyNet models, running 40 additional training epochs (20 for the TSP). To optimize GPU memory utilization, we adjust the batch size separately for each problem and its dimensions.
We categorize the evaluated algorithms into two groups: unguided and guided methods. Unguided algorithms generate solutions independently, while guided methods incorporate high-level search component capable of navigating the search space. For a comparison to unguided algorithms, we compare PolyNet to POMO and the Poppy approach with population size of 8. To ensure fairness we retrain Poppy using the same training setup as for PolyNet. Note that POMO has already been trained to full convergence and does not benefit from additional training (see Figure 33 For all approaches, we sample 64 x n solutions per instance (except for POMO using greedy solution generation). For our comparison to guided algorithms, we use PolyNet with EAS and compare it with POMO combined with EAS (Hottung et al., 2022) and SGBS (Choo et al. 2022). For PolyNet, we sample 200 8 n solutions per instance over the course of 200 iterations. Furthermore, we compare to some problem-specife approaches that are explained below. Note that we provide additional search trajectory plots in Appendix Results for the FFSP can be found in Appendix
TSP 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. (202T) for n= 150 and 7 = 200. For n 300, we generate new instances. As baseline, use the exact solver Concorde (Applegate et al. (0066) and the heuristic solver LKH3 (Helsgaun) 2017). Additionally, we also compare to DPDP (Kool et al. 2022b). COMPASS (Chalumeau al. (2023), and the diversity-focused method MDAM (Xin et al.) 2021
with beam search width of 256.
Table D provides our results on the TSP, showing clear performance improvements of PolyNet during fast solution generation and extensive search with EAS for all considered instance sets. For TSP instances with 100 nodes, PolyNet achieves a gap that is practically zero while being roughly 120 times faster than LKH3. Furthermore, on all four instance sets, PolyNet with unguided solution sampling finds solutions with significantly lower costs in comparison to guided learning approaches while reducing the runtime by factor of more than 100 in many cases.
CVRP Similar to the TSP, we use the test sets from Kool et al. (2019) and Hottung et al. (021)) As baseline, we use LKH3 (Helsgaun) 2000) and the state-of-the the-art (OR) solver HGS (Vidal et al.) 2012; Vidal (002)). We compare to the same learning methods as for the TSP with the addition of DACT (Ma et al. 2021)
7

---

Published as a conference paper at ICLR 2025
Table 2: Search performance results for CVRP.
Test (10K instances)
Test (1K instances)
Generalization (1K instances)
Method
Ri.
Meval 100
ft Neval 200
Tlgy
100, neval
= 150
n Meval
300
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
HGS
15.563
54h
21.766
17h
19.055
9h
27.737
46h
LKH3
15.646
0.53%
6d
22.003
1.09%
25h
19.222
0.88%
20h
28.157
1.51%
34h
Unguided
POMO greedy
15.754
1.23%
Im 22. 194
1.97%
<Im
19.684
3.30%
<Im 28.627
3.21%
Im
sampling
15.705
0.91%
5m
22.136
1.70%
3m
20.109
5.53%
1m
28.613
3.16%
9m
Poppy
15.685
0.78%
5m
22.040
1.26%
3m
19.578
2.74%
1m
28.648
3.28%
8m
PolyNet
15.640
0.49
5m
21.957
0.88% %
3m
19.501
2.34%
1m 28.552
2.94%
8m
DACT
15.747
1.18%
22h
19.594
2.83%
16h
DPDP
15.627
0.41%
23h
19.312
1.35%
5h
Guided
COMPASS
15.594
0.20%
4h
19.313
1.35%
1h
MDAM
15,885
2.07%
5h
19.686
3.31%
1h
POMO
EAS
15.618
0.35%
6h
21.900
0.61%
3h
19.205
0.79%
2h
28.053
1.14%
12h
SGBS
15.659
0.62%
10m
22,016
1.15%
7m
19.426
1.95%
28.293
2.00%
22m
SGBS&EAS
15.594
0.20%
6h 21.866
0.46%
4h
19.168
0.60%
2h
28.015
1.00%
12h
PolyNet EAS
15.584
0.14%
4h
21.821
0.25%
2h
19.166
0.59%
1h
27.993
0.92%
9h
Table 3: Search performance results for CVRPTW.
Test (10K instances)
Test (1K instances)
Generalization (1K instances)
Method
Tee-
Neval 100
Mer
Neaal 200
Tkp-
100,
Peeat
150
Ber 200,
Meeal
300
Obj. Gap
Time
Obj. Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
VRP
12,534
39h 18.422
11h 17,408
9h
25,733
26h
Unguided
POMO greedy
13,120
4.67%
Im
19,656
6.70%
Im
18,670
7.25%
<lm
28,022
8.90%
2m
sampling
13,019
3.87%
7m
19.531
6.02%
4m
18,571
6.68%
28,017
8.88%
13m
Poppy
12,969
3.47%
5m
19,406
5.34%
3m
18,612
6.91%
2m
28,104
9.22%
10m
PolyNet
12,876
2.73%
19,232
4.40%
3m
18,429
5.86%
27,807
8.07%
10m
Guided
POMO
EAS
12,762
1.81%
6h
18,966
2.96%
17,851
2.54%
2h
26.608
3.40%
14h
SGBS
12,897
2.89%
12m
19,240
4.44%
8m
18,201
4.55%
4m
27,264
5.95%
25m
SGBS-EAS
12.714
1.43%
7h
18,912
2.66%
4h
17,835
2.45%
2h
26,651
3.57%
15h
PolyNet EAS
12,654
0.96%
5h
18,739
1.72%
3h
17701
1.68%
1h
26,504 3.00%
10h
The CVRP results in Table 2 once again indicate consistent improvement across all considered problem sizes. Especially on the instances with 100 and 200 customers, PolyNet improves upon the state-of-the-art learning- based approaches by reducing the gap by more than 30% during fast solution generation and extensive search. Also note that PolyNet significantly outperforms the other diversity-focused approaches Poppy and MDAM.
the state-of-the-art CO solver VRP (Version 0.5.0) (Wouda et al. 2024) as a baseline stopping the search after 1,000 iterations without improvement. We compare POMO implementation that we adjusted solve the CVRPTW by extending the node features with the time windows and the context information used at each decoding step by the current time point. These models are trained for 50,000 epochs, mirroring the training setup used for the CVRP.
CVRPTW For the CVRPTW,
Table 3 presents the CVRPTW results, demonstrating PolyNet's consistent and superior performance across all settings compared to Poppy and POMO (with SGBS and EAS). Notably, for instances with 100 customers, PolyNet matches almost the CO solver VRP with a gap below 1%.
4.3 DIVERSITY
Does PolyNet's training encourage diversity? To assess the effectiveness of our diversity mech- anism, we conduct short training runs of PolyNet for the TSP, CVRP, and CVRPTW with varying values of K. As baseline report results for the training of the POMO model. For all runs, we use a batch size of 480 and a learning rate set at 10 To ensure stable initial state for training runs, we initialize the PolyNet layer weights to
start all runs from trained POMO model. For PolyNet, zero, minimizing initial randomness. During training, we perform regular evaluations on a separate validation set of 10 000 instances, sampling 800 solutions per instance.
8

---

Published as a conference paper at ICLR 2025
TSP
CVRP
CVRPTW
1:085
15.78
13165
7.783
13110
15.74
13075
Poly R
1.773
19000
20
10P
10
10'
10
30
10'
10P
10
61
Pureurage of Unoque Sclatoon
128
50
194
POSI
Farced
40
Five
Move
88
30'
10
10P
10
10
10'
Triiiin Progres (In Hatdiani)
Training Prngussa Harches)
Thiniing Prognes Butcioo)
Figure 3: Validation performance during training (log scale).
Table 4: Solution diversity measured using avg. broken pairs distance.
Table 5: Ablation results for free first move selection.
TSP Gap
CVRP Time
CVRPTW Time
Method
Time
Gap
Gap
Method
TSP
CVRP
CVRPTW
PolyNet
4.621
18:535
19,969
PolyNet
Free first move Forced first move
0.000%
0.006%
4m
4m
0.59%
0.49%
5m
5m
3.00%
2.73%
5m 6m
POMO
2,400|
16.785
18. 162
Poppy
0.015%
4m 0.78%
5m
3.47%
Sm
Our evaluation tracks the cost of the best solution and the percentage unique solutions among the 800 solutions per instance. Figure presentt the evaluation results. Across all three problems, we observe a clear trend: higher values of K lead to a more rapid reduction in average costs on the validation set and are associated with greater percentage of unique solutions. Note that POMO does not benefit from further training. These results underscore the effectiveness of our approach in promoting solution diversity and improving solution quality.
Does PolyNet generate diverse solutions at test time? In this experiment we evaluate the diversity of PolyNet test time. As baseline we use the POMO approach, which enforces diverse solution generation by forcing the first action. For each test instance, we sample 100 solutions with both approaches and calculate the average broken pairs distance (Prins) 2009), which is established method to measure diversity for routing problem solutions (see, e.g.. Vidal et al. (2012). The broken pairs distance d( d(A, B) for two solutions A and B is the number of edges of A that not in B. We measure the diversity of a set of solutions using the average across the broken pairs distances between all solution pairs of the set. The results shown in Table 4 confirm that PolyNet is able to generate more diverse solutions than POMO at test time. An additional visual comparison of the differences in solution diversity between POMO and PolyNet can be found in Appendix D
Does PolyNet encourage useful diversity? As discussed in the introduction, solution diversity alone is neither inherently beneficial nor difficult to achieve (e.g., by generating random solutions). What truly matters is that the diversity is useful, meaning it contributes to finding high-quality solutions. To assess the diversity of PolyNet we conduct two separate experiments.
First, we evaluate the importance of each of the K learned strategies at test time by counting how often each strategy finds the best solution across 10000 test instances. The results, shown in Figure 4 indicate that all K strategies contribute significantly to performance. Even the least effective strategies identify the best solution on 544, 61, and 54 instances for the TSP, CVRP, and CVRPTW, respectively, Note that for the TSP, multiple strategies often converge to the same best solution, likely because most instances are solved to optimality. However, for the CVRP and CVRPTW, the best solution for instance is typically found by only one strategy. These results demonstrate that all learned strategies are able to generate high-quality solutions and that all strategies contribute meaningfully to the overall sampling performance of PolyNet.
9

---

Published as a conference paper at ICLR 2025
TSP
CVRP
CYRPPW
Des. Sohrione Forni
1000
1000
1000
6001
600
400
2000
Sourch Strmlogy
Smarch Stewwoggy
Seurch Strnitggr
Figure 4: Contribution of different search strategies. Strategies are sorted based on their contribution.
TSP
OVRP
CVRPTW
15000
10003
6000
10002
7503
Supibe
6000
5003
5100
2000
2500
Uniqqe
Unique
Unique Nodre
Figure 5: Frequency plots for the number of unique first nodes.
Second, we evaluate the number of distinet first nodes selected by the K different strategies of PolyNet. This provides insights into the diversity achieved by PolyNet, particularly in comparison to POMO, which enforces diversity by selecting different first actions. As shown in Figure 5 PolyNet selects fewer distinct first nodes than POMO. On average, PolyNet selects 24.5, 3.8, and 7.0 distinct first nodes for the TSP. CVRP, and CVRPTW, respectively. Despite selecting fewer different first nodes, PolyNet is able to generate solutions that are more diverse overall than those generated by POMO, shown in Table This suggests that PolyNet achieves diversity through means other than enforcing the first action.
4.4 ABLATION STUDY: FORCING THE FIRST MOVE
PolyNet does not force diverse first construction actions and relies solely on its built-in diversity mechanism to select the first node. To assess this approach, compare the performance of PolyNet with and without forced first move selection when sampling 64 100 solutions per instance.
shows the results for all problems with 100. Remarkably, across all scenarios, allowing PolyNet to select the first move yields superior performance compared to forcing the first move. Furthermore, PolyNet with forced first move selection outperforms Poppy (which also enforces the first move), underscoring that PolyNet's single-decoder architecture delivers better results.
5 CONCLUSION
We introduced the novel approach PolyNet, which is capable of learning diverse solution strategies using single-decoder model. PolyNet deviates from the prevailing trend in neural construction methods, in which diverse first construction steps are forced to improve exploration. Instead, it relies on its diverse strategies for exploration, enabling its seamless adaptation to problems where the first move significantly impacts solution quality. In our comprehensive evaluation across four problems, including the more challenging CVRPTW, PolyNet consistently demonstrates performance improvements over all other learning-base based methods, particularly those focused diversity.
Regarding our approach's ' limitations, we acknowledge that the computational complexity of the attention mechanism
employ restricts its applicability to instances with less than 1000 nodes. However, it is essential to emphasize that the problem sizes examined this paper for the CVRP(TW) remain challenging for traditional CO solvers and are highly significant in real- world upplications. Furthermore, we note that the black-box nature of the PolyNet's decision decision-mmkknn may be unacceptable in certain decision contexts.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
André Hottung was supported by the Deutsche Forschungsgemeinschat (DFG, German Research Foundation) under Grant No. 521243122. Additionally, we gratefully acknowledge the funding of this project by computing time provided by the Paderborn Center for Parallel Computing (PC2). Furthermore, some computational experiments in this work have been performed using the Bielefeld GPU Cluster. We thank the HPC.NRW team for their support.
REFERENCES
David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde TSP solver, 2006.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural Combinatorial Optimization with Reinforcement Learning. arXiv: 1.09940, 2016.
Federico Berto, Chuanbo Hua, Junyoung Park, Laurin Luttmann, Yining Ma. Fanchen Bu, Jiarui Wang, Haoran Ye, Minsu Kim, Sanghyeok Choi, Nayeli Gast Zepeda, André Hottung, Jianan Zhou, Jieyi Bi, Yu Hu, Fei Liu, Hyeonah Kim, Jiwoo Son, Haeyeon Kim, Davide Angioni, Wouter Kool, Zhiguang Cao, Jie Zhang, Kijung Shin, Cathy Wu, Sungsoo Ahn, Guojie Song, Changhyun Kwon, Lin Xie, and Jinkyoo Park. RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark. arXiv:2306.17100, 2024a.
Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, André Hottung, Niels Wouda, Leon Lan, Junyoung Park, Kevin Tierney, and Jinkyoo Park. Routefinder: Towards foundation models for vehicle routing problems. arXiv:2406. 15007, 2024b.
Bernd Bischl, Pascal Kerschke, Lars Kotthoff, Marius Lindauer, Yuri Malitsky, Alexandre Fréchette, Holger Hoos, Frank Hutter, Kevin Leyton- Kevin Tierney, et al. ASlib: A benchmark library for algorithm selection. Artificial Intelligence, 237:41-58, 2016.
Christian Blum and Andrea Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Comput. Surv., 35(3):268-300 -38,, Sep 2003.
Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmect Kohli. Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis. International Conference on Learning Representations, 2018.
Cristian Cataldo-Díaz, Rodrigo Linfati, and John Willmer Escobar. Mathematical models for the electric vehicle routing problem with time windows considering different aspects of the charging process. Operational Research, 24(1):1, 2024.
Felix Chalumeau, Shikha Surana, Clément Bonnet, Nathan Grinsztajn, Arnu Pretorius, Alexandre Laterre, and Thomas D Barrett. Combinatorial Optimization with Policy Adaptation using Latent Space Search. In Neural Information Processing Systems, 2023.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, pp. 6278-6289, 2019.
Jinho Choo, Yeong-Das Kwon, Jihoon Kim, Jeongwoo Jac, André Hottung, Kevin Tiemey, and Youngjune Gwon. Simulation guided beam search for neural combinatorial optimization. Advances in Neural Information Processing Systems, 35:8760-88 8772, 2022.
CPLEX- CPLEX-Optimizn AedimizationnStudio V20.1: User's Manual for CPLEX, 2020.
Paulo da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Eren Akçay. Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning. In Asian Conference on Machine Learning, 2020.
Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Mare Andreoli. Bq-nco: Bisimula- tion quotienting for efficient neural combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is All You Need: Learning Skills without& Reward Function. arXiv: (tlo::8822000700 2018.
11

---

Published as a conference paper at ICLR 2025
Jonas K Falkner and Lars Schmidt-Thieme Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention. arXiv:2006.09100, 2020.
Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large TSP instances. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 7474-7482, 2021.
Michel Gendreau, Jean- Potvin, et al. Handbook of metaheuristies, volume 2. Springer, 2010.
Robert Givan, Thomas L. Dean, and Matthew Greig. Equivalence notions and model minimization in Markov decision processes. Artificial Intelligence, 147:163-223, 2003.
Nathan Grinsztajn, Daniel Furelos- Blanno. Shikha Surana, Clément Bonnet, and Tom Barrett. Winner takes it all: Training performant rl populations for combinatorial optimization. Advances in Neural Information Processing Systems, 36:48485-48509 2023.
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, and Yota Otachi. Computing diverse shortest paths efficiently: A theoretical and experimental study. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 3758-3766 2022.
Keld Helsgaun. An effective implementation of the Kin-Kerni traveling salesman heuristic. European Journal of Operational Research, 126:106-131 06-130, 2000.
Keld Helsgaun. An extension of the Ken--eiiigaan-ellgammm TSP solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 2017.
André Hottung and Kevin Tiemny. Neural Large Neighborhood Search for the Capacitated Vchicle Routing Problem. In European Conference on Artificial Intelligence, pp. 443 450, 2020.
André Hottung, Bhanu Bhandari, and Kevin Tierney Learning a Latent Search Space for Routing Problems using Variational Autoencoders. In International Conference on Learning Representa- tions, 2021.
André Hottung, Paula Wong-Chung, and Kevin Tierney. Neural deconstruction search for vehicle routing problems. arXiv:2501.03715, 2025.
André Hotung, Yeong-Dae Kwon, and Kevin Tierney. Efficient Active Search for Combinatorial Optimization Problems. International Conference on Learning Representations, 2022.
Chuanbo Hua, Federico Berto, Jiwoo Son, Seunghyun Kang, Changhyun Kwon, and Jinkyoo Park. CAMP: Collaborative Attention Model with Profiles for Vehicle Routing Problems. In Proceedings of the 2025 International Conference Autonomous Agents and Multiagent Systems (AAMAS), 2025. https: / htt//ggttuuuut thub. com/ a 4co/ camp
Ting Huang, Yue-Jiao Gong, Sam Kwong, Hua Wang, and Jun Zhang. A niching memetic algorithm for multi-solution traveling salesman problem. IEEE Transactions Evolutionary Computation, 24(3):508-52,, 2019.
Ali Aghadavoudi Jolfaei and Mahdi Alinaghian. Multi-depot vehicle routing problem with roaming delivery locations considering hard time windows: Solved by a hybrid els-Ins algorithm. Expert Systems with Applications. 255:124608, 2024.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem. arXiv:1906.01227, 2019.
Hyconah Kim, Minsu Kim, Sungsoo Ahn, and Jinkyoo Park. Symmetric Replay Training: En- hancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimization. In International Conference on Machine Learning, 2024.
Minsu Kim, Jinkyoo Park, and Joungho Kim. Learning Collaborative Policies to Solve NP-hard Routing Problems. In Neural Information Processing Systems, 2021.
Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization. In Neural Information Processing Systems, 2022.
12

---

Published as a conference paper at ICLR 2025
Wouter Kool, Herke van Hoof, and Max Welling. Attention, Learn to Solve Routing Problems! In International Conference on Learning Representations. 2019.
Wouter Kool, Laurens Blick, Danilo Numeroso, Yingqian Zhang, Tom Catshock, Kevin Tierney, Thibaut Vidal, and Joaquim Gromicho. The EURO Meets NeurlPS 2022 Vehicle Routing Compe- tition. In Proceedings of the NeurlPS 2022 Competitions Track, 2022a.
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep Policy Dynamic Programming for Vehicle Routing Problems. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2022b.
Yeong- Dae Kwon, Jinho Choo, Byoungjip Kim, Iijoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. In Advances in Neural Information Processing Systems, volume 33, pp. 21188-22 2198, 2020.
Yeong-Dat Dae Kwon, Jinho Choo, Iijoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. In Neural Information Processing Systems, 2021.
Gonzalo Lera-Romero, Juan José Miranda Bront, and Francisco Soulignac. A branch-cut-and-pricc algorithm for the time-dependent electric vehicle routing problem with time windows. European Journal of Operational Research, 312(3):978 999-9997899999 2024.
Chenghao Li, Chengjie Wu, Tonghan Wang, Jun Yang, Qianchuan Zhao, and Chongjie Zhang. Celebrating Diversity in Shared Multi-Agent Reinforcement Learning. In Neural Information Processing Systems, 2021.
Jingwen Li, Yining Ma, Zhiguang Cao, Yaoxin Wu, Wen Song, Jie Zhang, and Yeow Meng Chee. Learning Feature Embedding Refiner for Solving Vehicle Routing Problems. IEEE Transactions on Neural Networks and Learning Systems, 2023a.
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization. In Neural Information Processing Systems, 2023b.
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization. In Neural Information Processing Systems, 2023.
Yining Ma, Jingwen Li. Zhiguang Cao. Wen Song, Le Zhang, Zhenghua Chen, and Jing Tang. Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer. In Neural Information Processing Systems, 2021.
Yining Ma. Zhiguang Cao, and Yeow Meng Chee. Learning Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural O-Opt. In Neural Information Processing Systems, 2023.
Samir W Mahfoud. Niching methods for genetic algorithms. University of Illinois at Urbana- Champaign, 1995.
Yimeng Min, Yiwei Bai, and Carla P Gomes. Unsupervised Learning for Solving the Travelling Salesman Problem. In Neural Information Processing Systems, 2023.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pp. 9839-9849, 2018
Thomas Pierrot and Arthur Flajolet. Evolving Populations of Diverse RL Agents with MAP-Elites. In International Conference on Learning Representations, 2023.
Christian Prins. Two memetic algorithms for heterogeneous fleet vehicle routing problems. Engineer- ing Applications of Artificial Intelligence, 22(6):916-97) 928, 2009.
Eduardo Queiroga, Ruslan Sadykov, Eduardo Uchoa, and Thibaut Vidal. 10,000 optimal CVRP solutions for testing machine learning based heuristics. In AAAI-22 Workshop on Machine Learning for Operations Research (MI40R). 2022.
13

---

Published as a conference paper at ICLR 2025
Archit Sharma, Shixiang Gu, Sergey Levine, Vikash Kumar, and Karol Hausman. Dynamics-aware unsupervised discovery of skills. arXiv:1907.01657, 2019.
Marius M Solomon. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2):254-265, 1987.
Zhiqing Sun and Yiming Yang. DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization. In Neural Information Processing Systems, 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is All you Need. In Advances in Neural Information Processing Systems, volume 30, 2017.
Thibaut Vidal. Hybrid genetic search for the CVRP: Open-source implementation and SWAP* Neighborhood. Computers & Operations Research, 140: 145:40,,,3, 2022.
Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, Nadia Lahrichi, and Walter Rei. A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems. Operations Research, 60(3):61 1-624, 2012.
Oriol Vinyals. Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pp. 2692-2700, 2015.
Niels A. Wouda, Leon Lan, and Wouter Kool. PyVRP: a high-performance VRP solver package. INFORMS Journal Computing, 36(4):943-955, 2024.
Shuang Wu, Jian Yao, Haobo Fu, Ye Tian, Chao Qian, Yaodong Yang, QIANG FU, and Yang
Wei. Quality-Similass Diversity via Population Based Reinforcement Learning. In The Eleventh International Conference on Learning Representations, 2023.
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning Improvement Heuristics for Solving Routing Problems. IEEE Transactions on Neural Networks and Learning Systems, 2019.
Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, and Jiang Bian. Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems. In International Conference on Machine Learning, 2024.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 12042-12049, 2021.
Jie Zhang, Yanfeng Li, and Zhaoyang Lu. Multi-period vehicle routing problem with time win- dows for drug distribution the epidemic situation. Transportation Research Part C: Emerging Technologies, 160: 104484, 2024.
Yunbo Zhang, Wenhao Yu, and Greg Turk. Learning novel policies for tasks. International Conference on Machine Learning, pp.
PMLR, 2019.
14

---

Published as a conference paper at ICLR 2025
A EXPERIMENTAL RESULTS FOR THE FFSP
We examine the flexible flow shop problem (FFSP) to further demonstrate PolyNet's versatility beyond routing problems, and the generality of the technique beyond the POMO architecture. In the FFSP, set of jobs must be processed in series of stages, with each stage comprising multiple machines that each require different processing times. machine cannot process more than one job at the same time. The objective is determine a job schedule with the shortest makespan. We generate problem instances randomly according to the method in Kwon et al. (2021). We experiment on FFSP instances with 20, 50, and 100 jobs, where each instance consists of 3 stages and each stage has 4 machines.
Network architecture We use a neural network that extends the architecture of MatNet (Kwon al. 2021). More concretely, we introduce residual block for each of the decoding networks. In all experiments, the PolyNet layers in every block comprise two linear layers, each with a dimensionality 256.
Training To train the PolyNet models, we use learning rate set to 10 and batch sizes of 256, 128, and 32 for instances comprising n = 20, 50, and 100 jobs, respectively. We set the parameter K to 24 across all problem sizes. The training runs start from trained MatNet models and continue for 100 (20 for = 100) epochs, with each epoch comprising 24 x 10 solution rollouts.
Search performance For the FFSP, we use the randomly generated test sets from Kwon et al. (2021) and comparison algorithms. In addition MatNet (Kwon et al.) 2021), I we compare our method to CPLEX and metaheuristic solvers. Table 66 provides the results for the FFSP. The gaps are reported with respect to PolyNet with x 128 augmentation result, as optimal solutions are not available. The results demonstrate PolyNet's consistent improvement in performance across all problem sizes. Notably, PolyNet outperforms MatNet-based solvers for the FFSP on all problem sizes and produces solutions of even higher quality within similar run times. Given the different architecture of MatNet compared to those used for routing problems, the results highlight that the performance gains from PolyNet are not confined to a specific network architecture. Moreover, these gains extend beyond routing problems, indicating PolyNet's broad applicability across various CO problems.
Studio 2020) with mixed-integer programming models
Table 6: Search performance results for FFSP.
FFSP20
FFSP50
FFSP100
Method
MS
Gap
Time
MS Gap
Time
MS Gap
Time
CPLEX (60s)
46.4
21.5
(17h)
X
CPLEX (600s)
36.6
11.7
(167h)
Random
47.8
22.9
(1m)
93.2
44
(2m)
167.2
78.0
(3m)
Shortest Job First
31.3
6.4
(40s)
57.0
7.8
(1m)
99.3
10.1
(2m)
Genetic Algorithm
30.6
5.7
(7h)
56.4
7.2
(16h)
98.7
9.5
(29h)
Particle Swarm Opt.
29.1
4.2
(13h)
55.1
5.9
(26h)
97.3
8.1
(48h)
MatNet
27.1
2.2
(Ss)
$1.5
2.3
(9s)
91.6
2.4
(17s)
PolyNet
26.7
1.8
(5s)
51.0
1.8
(10s)
91.2
2.0
(18s)
MaiNet (x 128)
25.4
0.5
(3m)
49.6
0.4
(8m)
89.8
0.6
(19m)
PolyNet 128)
24.9
(4m)
49.2
(9m)
89.2
(23m)
B ABLATION STUDY: POLYNET LAYERS
To assess the influence of our new PolyNet layers, we perform an ablation experiment in which we systematically remove these additional layers during the training. In this modified version of PolyNet, we add the vector v directly to the output of the masked multi-head attention mechanism (shown in Figure ( To achieve this, the vector is prro-pdddeddPe to match the necessary dimensions. Note that this altered PolyNet configuration has exactly the same number of total model parameters as the POMO model.
15

---

Published as a conference paper at ICLR 2025
TSP
CVRP
CVRPTW
13125
POMO
7.780
POMO with
7,780
15.74
13100
Adiied Lagers
Poly w/o
19775
Adhied Lagers
7.715
PulyNet wish
Adiied Layers
15.70
5
10
20
10
20
10
15
20
Trainnng Progress (in Epocie)
Triining Progress (in. Equcias)
Traizing Progress (in. Epucias)
Figure 6: Validation performance during training.
For a fair comparison we also extend the baseline POMO model by our additional PolyNet layers. The modified POMO model comprises the same number of model parameters as our PolyNet architecture. Note that the modified POMO model does not accept a vector c. Instead, the PolyNet layers directly receive the output of the masked multi-head attention mechanism.
We train all models for 20 epochs using the same training hyperparameters as for our main training run described in Section 4.2 After each epoch evaluate the model performance our validation set that comprises 10, 000 instances, sampling 800 solutions per instance.
Figure shows the validation costs over the course of the training. On all three problems, PolyNet without the added layers performs worse than its original version, which demonstrates the importance of the PolyNet layers. Nonetheless, even PolyNet without the added layers is able to significantly outperform POMO with additional layers.
C POLYNET TRAINING: WARM-START VS. COLD-START
In all of our previous experiments, initialize the training process using pre-trained POMO model. To assess the implications of this setup. we conduct additional training runs where models are either warm-started or trained from scratch. These runs utilize identical hyperparameters as our primary training sessions, but extend training for total of 400 epochs. It's worth noting that these extended training runs span several weeks and that the additional insights gained by even longer training runs are likely limited.
F iillustrates the validation performance throughout these training sessions. We observe notable benefits from warm-starting the training process. Specifically, the CVRP and CVRPTW tasks, models initialized from cold start consistently exhibit poorer performance even after 400 epochs of training. This discrepancy is particularly evident in the CVRPTW task, where the lower learning rate of 10 -5 Icads to slower training progress. Only in the TSP task does the performance of the cold-started model converge with that of the warm-started model after 400 epochs. We thus infer that while PolyNet can indeed be trained from scratch, warm-stan warm-starting the training process is advisable to mitigate computational costs.
TSP
CVRP
CVRPTW
15.76
13400
7.774
15.74
1:3000
7,772
15.72
13200
Sold-Star: Start
7,770
15.70
13100
7.768
15.08
13000
Training Progresa (In Ppochs)
Training Progress (in Epochs)
Tradnnn Progros (in Pgochs)
Figure 7: Validation performance during training: Starting training from scratch (cold-start) vs. starting from trained POMO model (warm-start).
16

---

Published as a conference paper at ICLR 2025
D SOLUTION UNIQUENESS VS. COSTS PLOTS
In this experiment, we compare the solutions generated by POMO to those generated by PolyNet with respect their cost and their uniqueness an instance-by-instance basis. More specifically, for a subset of test instances, we sample 100 solutions per instance with both approaches and compare the solutions found on the basis of their uniqueness and their cost. We calculate the uniqueness of solution by using the average of the broken pairs distance (Prins 2009) to all other 99 generated solutions.
Figures 10 shows the results for the first six TSP, CVRP, and CVRPTW test instances. PolyNet generates more unique solutions on most instances. Especially on the TSP the solutions from PolyNet are much more diverse, however this diversity occasionally comes at the expense of solution quality. Since we ultimately only care about the solution with the minimal costs in the generated solution set and, not the average solution quality, this is not limitation of the method. PolyNet is only able to increase its performance in the minimum cost case by sometimes trying out solutions that greedier method, like POMO, ignores.
POMO
Noly
POMO
PolyNet
POMO
PolyNet
Sclation Tnaiegannoo
Soletton Unoquenees
75
8.0
8.5
9.0
8.0
9.5
10.0
5.0
8,0
9.0
Clest
Oost
(a) Instance
(b) Instance 2
(c) Instance 3
POMO
Not
POMO
PolyNet
POMO
Solmoon Unirpaoos
Sclutioo Utalipooeess
Sobmtto Unteueton T
Cost
Coot
(d) Instance
Instance
(I)
Instance
Figure 8: Solution diversity costs for the TSP.
17

---

Published as a conference paper at ICLR 2025
POMO
PolyNet
POMO
Poly
POMO
Nol
Salasion Unaguenaaon
22
Subtsoon Unaquemset
16
15.2
14.0
15.0
16.5
14.5
Cost
Cost
Cost
(a) Instance
(b) Instance
(c) Instance
PoleNet
POMO
PolyNet
POMO
Poly
Solustoo Uaiquaaaas
Sabstoon Unequesaee
18
10
16
10.75
(d) Instance
Instance 5
(f) Instance 6
Figure 9: Solution diversity costs for the CVRP
POMO
POMO
PolyNet
POMO
Poly
27.0
Sdatin Uiiquaoss
25.0
Sclerien Unaqueasoe
14
17000
18000
1900
13000
13900
1100
1490
Oci
Chock
Clst
(a) Instance
(b) Instance
(c) Instance
POMO
Noly
POMO
PoleNet
POMO
Poly
26
Saletio Itlquaoos
Saletton Iniqueeeo
24
(d) Instance
Instance S
(l) Instance 6
Figure 10: Solution diversity vs. costs for the CVRPTW
18

---

Published as a conference paper at ICLR 2025
E SEARCH TRAJECTORY ANALYSIS
In Figure [1 we show the search trajectories for models trained with varying values K across all three routing problems featuring 100 nodes. The search process employs solution sampling without EAS and without the use of instance augmentations. These models used for the search undergo training for 150 epochs (except for the CVRP, where the training spans 200 epochs).
It is evident across all three problems that the search does not achieve full convergence within 10,000 iterations. This observation once again underscores PolyNet's capability discover diverse solutions, enabling it to yield improved results with extended search budgets. It's important to note that this experiment, including model training, has not been replicated with multiple seeds. Nevertheless, the results suggest that models trained with larger K values benefit more from longer search budgets compared to models trained with smaller values.
CVRPTW
7.7665
12980
15,00
K
7.7660
15.68
129
178
7,7866
15.67
12900
0
2500
5000
7500
10000
0
2500
5000
7500
10000
2500
5000
7500
10000
Scarch. Progress (in Sumpled Solutions)
Search Progress (in Sampled Solutions))
Search Progres (in Sacupled Solutions]
Figure 11: Search trajectories.
F CVRPTW INSTANCE GENERATION
We generate instances for the CVRPTW with the goal of including real-world structures. To achieve this, we employ a two-step approach. First, we use the CVRP instance generator developed by Queiroga et al. (2022) to produce the positions and demands of customers. Subsequently, we follow the methodology outlined by (Solomon (1987) to create the time windows. We generate different instance sets for training, validation, and testing.
Customer positions are generated using the clustered setting (configuration 2) and customer demands are based on the small, large variance setting (configuration 2). The depot is always centered (configuration 2). It is worth noting that the instance generator samples customer positions within the 2D space defined by [0, 999]2. Independently from the instance generator, vehicle capacities are set 50 for instances involving fewer than 200 customers and increased to 70 for instances with 200 or more customers.
To generate the time windows, adhere to the procedure outlined by Solomon 1987) for instances with randomly clustered customers (i.e., we do not utilize the 3-opt technique to create reference routes). We randomly generate time windows (ex, 4) for all customers, and set 2400 the latest possible time for a vehicle to return to the depot. The time window generation process, as described in Solomon (197), limits the time windows to ensure feasibility (c.g., by selecting 4 so that there is always sufficient time for servicing the customer and returning to the depot). The center of the time window uniformly sampled from range defined by these limits. We set the maximum width of the time window to 500 and the service duration to 50. These parameter values have been deliberately chosen to strike a balance between the constraints of vehicle capacity and time windows, requiring both aspects to be considered during the solution generation proces.
19


Reviews:
[{"review_id": "52bCcHVgXS", "reviewer": "Reviewer_rRFp", "summary": "PolyNet introduces a novel approach to enhancing exploration in neural combinatorial optimization (CO). Unlike traditional methods that enforce diversity via handcrafted rules, PolyNet employs a single-decoder model that inherently learns multiple strategies, facilitating more effective search and solution quality. The paper demonstrates PolyNet's superior performance across several benchmark CO problems, such as TSP, CVRP, and CVRPTW, outperforming state-of-the-art methods both in speed and solution quality.", "questions": "1. How would PolyNet perform when extended to non-routing CO problems, such as job scheduling or knapsack problems?\n\n2. Can you elaborate on the potential methods for improving PolyNet’s scalability to handle larger problem instances?\n\n3. What are the specific limitations of PolyNet’s inherent diversity mechanism when applied to problem instances with different statistical properties?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The use of a single-decoder model that can learn multiple strategies simplifies the training pipeline and reduces computational overhead compared to multi-decoder systems.\n\n- The model's training schema, which emphasizes inherent diversity, makes it adaptable to various CO problems beyond simple routing tasks.\n\n- The authors provide useful insights into the impact of their design choices, such as the effectiveness of not forcing diverse first moves.", "weaknesses": "- While starting from pre-trained models boosts training efficiency, this reliance could limit applicability in cases where such pre-training is not feasible or available.\n\n- While PolyNet demonstrates strong results in routing tasks, its effectiveness in other CO problem domains (e.g., scheduling or knapsack) has not been deeply explored.\n\n- The paper does not discuss how PolyNet handles instances where input data is noisy or incomplete, a common occurrence in practical applications.\n\n- The impact of different hyperparameter settings on model performance is not fully analyzed, which could be critical for real-world applications requiring fine-tuning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bw3uLZp6Dy", "reviewer": "Reviewer_rgaA", "summary": "To facilitate learning complementary solution strategies, this paper avoids forcing the initial action step. Instead, it enhances exploration by embedding it into the decoder as a bit vector. While experiments demonstrate performance improvements, the approach lacks novelty.", "questions": "1. The advantages of using bit vectors as supplementary vectors for insertion should be thoroughly analyzed, particularly in comparison to previous continuous potential vectors.\n2. In the experimental section, a more comprehensive explanation and analysis of performance concerning runtime are necessary.", "limitations": "", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "1. The paper is well-structured, presenting its content in a clear manner.\n2. A wide range of experiments are conducted to assess solution diversity.", "weaknesses": "1. The method of inserting additional vectors in the decoder is very similar to the idea of COMPASS [1], lacking sufficient innovation to significantly advance the field.\n2. The description of bit vectors is minimal, and there is no detailed analysis of how varying vector representations might impact performance.\n3. The fairness of comparing COMPASS with PolyNet+EAS in an experimental context is questionable.\n4. In [1], there is a big difference between COMPASS and EAS runtimes, but in this paper, PolyNet+EAS time is similar to COMPASS, please specify the reason.\n\n[1] Combinatorial optimization with policy adaptation using latent space search. NeurIPS 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lEgrkRMebP", "reviewer": "Reviewer_BPFA", "summary": "This study, grounded in the POMO framework, introduces a straightforward yet impactful component: PolyNet. The component takes as input the concatenation of a set of binary vectors and the output from the decoder's multi-head attention layers. After processing through a series of linear layers and activation functions, the output is directly added to the output of the decoder's multi-head attention layers, thereby directly influencing the probability distribution of node selection. Analysis from the paper indicates that the newly added module helps to enhance solution diversity without the need for mandatory starting point selection as in POMO. Additionally, the authors assert that PolyNet can be integrated with EAS, and significant performance improvements can be achieved by updating only the newly added modules.", "questions": "1. What is the design motivation behind the additional concatenated binary array $v$? Why can it significantly enhance diversity and optimality? If it were replaced with a column of random numbers, or if random perturbations were directly added to the input of the \"added layer,\" would the same effect be achieved?\n\n2. In Appendix Figure 6, a comparison is made between \"PolyNet w/o Added Layers\" and \"POMO with Added Layers.\" It would be better if a \"POMO\" without additional additions could be included for comparison. My question is, why does \"PolyNet w/o Added Layers\" perform significantly better than \"POMO with Added Layers\"? Is it due to differences in training methods? If so, it would be best to compare POMO with the new training method.\n\n3. Which contributes more significantly, the training method or the new structure?\n\n4. In combinatorial optimization, there is a class of problems specifically focused on diversity optimization, where multiple solutions need to be found simultaneously. Relevant papers include “Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study” and “A Niching Memetic Algorithm for Multi-Solution Traveling Salesman Problem.” The work presented in this paper seems particularly suited for such scenarios, and I hope to see more discussion on this topic.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The authors have clearly articulated the framework and implementation of the method, with smooth writing.\n2. The tables and figures are presented clearly, and the experiments are comprehensive.\n3. Testing PolyNet on various combinatorial optimization problems (TSP, CVRP, CVRPTW, FFSP) demonstrates the good generality of the method.\n4. (As claimed by the authors) their method performs exceptionally well on instances of scale 100, 200, and 300 (Tables 1-3).", "weaknesses": "PolyNet can enhance the diversity and optimality of solution sets, but the authors seem to lack an in-depth discussion on the principles behind the additional layers of PolyNet. This leaves me somewhat puzzled. The training process described in the paper adopts a method similar to Poppy, and the added linear layers, activation functions, and residual connections are common components in the Transformer architecture. The motivation for significant improvements by merely concatenating an additional binary array is not very clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8BXoTBJTI4", "reviewer": "Reviewer_qkCr", "summary": "This paper proposes PolyNet, which aims to reinforce the exploration training and testing of Nueral CO methods. In particular, a representive NCO method POMO is used as the playground in this paper. The idea behind this paper is quite simple: adding a neural network module which contains MLP layers besides the  main structure of POMO, termed PolyNet layer. PolyNet layer  provide exploration ability by letting its input as the node embeddings and a binary context coding. Using different binary context codings, the output of PolyNet layer add different information to the output of POMO hidden layers. By training on moderate instances, PolyNet show state-of-the-art performance on several CO problems (#nodes < 300). Besides, the authors demonstrate the exploration ability of PolyNet during the training and testing is different from the common practice in existing works: forcing diverse first action selection.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The idea behind PolyNet is simple yet effective. The methodology part is easy-to-follow. The experimental results for performance comparison on different CO problems are solid and convincing. The ablation studies that explain the solution diversity in PolyNet are with good demonstration.", "weaknesses": "There are two major weaknesses:\n\na) Related works are not well-organized. As a important part to let readers aware the background, the motivation and the priority of this paper, Neural CO methods should be organized in a way that these points are clearly outlined. \n\nb) Fow now, the scale of the CO problems PolyNet could address is no more than 300, which makes me curious about the performance of PolyNet on larger instances (#nodes > > 300). From my angle, the exploration ability is especially needed in large scale problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)