Generative Adversarial Training for Neural Combinatorial Optimization Models
Authors: Liang Xin
Wen Song
Zhiguang Cao
Jie Zhang
Venue: ICLR 2022 Submitted (2022)
Keywords: Deep Learning
Combinatorial Optimization Problem

Abstract: Recent studies show that deep neural networks can be trained to learn good heuristics for various Combinatorial Optimization Problems (COPs). However, it remains a great challenge for the trained deep optimization models to generalize to distributions different from the training one. To address this issue, we propose a general framework, Generative Adversarial Neural Combinatorial Optimization (GANCO) which is equipped with another deep model to generate training instances for the optimization model, so as to improve its generalization ability. The two models are trained alternatively in an adversarial way, where the generation model is trained by reinforcement learning to find instance distributions hard for the optimization model. We apply the GANCO framework to two recent deep combinatorial optimization models, i.e., Attention Model (AM) and Policy Optimization with Multiple Optima (POMO). Extensive experiments on various problems such as Traveling Salesman Problem, Capacitated Vehicle Routing Problem, and 0-1 Knapsack Problem show that GANCO can significantly improve the generalization ability of optimization models on various instance distributions, with little sacrifice of performance on the original training distribution.

Under review as a conference paper at ICLR 2022
GENERATIVE ADVERSARIAL TRAINING FOR NEURAL COMBINATORIAL OPTIMIZATION MODELS
Anonymous authors
Paper under double-blind review
ABSTRACT
Recent studies show that deep neural networks can be trained to learn good heuris- ties for various Combinatorial Optimization Problems (COPs). However, it re- mains great challenge for the trained deep optimization models to generalize to distributions different from the training one. To address this issue, we propose general framework, Generative Adversarial Neural Combinatorial Optimization (GANCO) which is equipped with another deep model to generate training in- stances for the optimization model, so to improve its generalization ability. The two models are trained alternatively in an adversarial way, where the generation model is trained by reinforcement learning to find instance distributions hard for the optimization model. We apply the GANCO framework to two recent deep combinatorial optimization models, i.e., Attention Model (AM) and Policy Opti- mization with Multiple Optima (POMO). Extensive experiments on various prob- lems such as Traveling Salesman Problem. Capacitated Vehicle Routing Problem. and ()-1 Knapsack Problem show that GANCO can significantly improve the gen- eralization ability of optimization models on various instance distributions, with little sacrifice of performance the original training distribution.
INTRODUCTION
Combinatorial Optimization Problems (COPs) are family of problems with the goal of finding the best one(s) from a finite set of solutions. Due to the considerably large solution space, many im- portant COPs are hard to solve, such as the vehicle routing problems (Toth & Vigo 2002). Exact algorithms based on branch-and-bound (Lawler Wood 1966) or variants can provide elegant theoretical guarantees but the worst-case computational complexity is exponential, hence impracti- cal for problems of medium and large sizes. In contrast, heuristic methods can usually attain good solutions in reasonable running time, which are often preferred in practical applications.
Traditional heuristics are designed based on expert knowledge for specific problems, which usually requires large amount of time and efforts to develop. These manually designed heuristics could suffer from relatively poor performance. Moreover, for less studied problems, sufficient expert knowledge may even be unavailable. Recent studies suggest that deep learning could greatly facili- tate in automating the design of heuristics, and alleviating the heavy reliance on expert knowledge. With the prior that the instances may follow certain distribution (e.g., locations locatioos in a routing problem may uniformly seatter in an area), deep models can be trained to learn heuristics in an end-to-end way (Dai al. 2017 Kool et al. 2019 Chen & Tian 2019). has been shown that these models perform well with relatively short running time on COP instances following the training distribution.
However, after the trained model is deployed. it could encounter many instances following unknown distributions different from the training one, especially for real-life applications. As shown in many existing works and our experiments, when applied to infer the instances following different distri- bution, the generalization performance of deep models gets much inferior, which severely hinders the practical use of the learned heuristics. Such mismatch between the training and testing distribu- tions is always an important issue for most learning based methods. Especially, for neural combi- natorial optimization (NCO) models, deep learning models are mostly trained on instances sampled from specific distributions and the solution quality intricately depends on the instance distributions. The generalization to instances with different distributions has been widely acknowledged for the importance (e.g., in Mazyavkina et al. (202T) and remains challenge.

---

Under review as a conference paper at ICLR 2022
To tackle this issue, propose the Generative Adversarial Neural Combinatorial Optimization (GANCO) framework which is model agnostic and generally applicable to various neural combi- natorial optimization models for solving different COPs. Instead of training an optimization model only on instances following the predefined distribution, another deep neural network is deployed as generation model to produce training instances following the distributions tion model performs poorly. The generation model and optimization model are trained alternatively in an adversarial way. Specifically, the generation model is trained by reinforcement learning to maximize the performance gap of the current optimization model on the generated instances with respect to a traditional non-learning baseline algorithm. The optimization model is trained in the original way but using the training dataset augmented with the newly generated instances to im- prove the generalization performance, i.e., to reduce the performance gap. As we will show in the experiments, the non-learning baseline algorithms do not need to be very strong or fast.
which the optimiza-
To demonstrate the effectiveness of the proposed GANCO framework, we apply it to a representative neural combinatorial optimization model, the Attention Model (AM. Kool et al. (2019)) various COPs including Traveling Salesman Problem (TSP), Capacitated Vehicle Routing Problem (CVRP), Orienteering Problem (OP). Prize Collecting TSP (PCTSP) and 0-1 Knapsack Problem (KP). In the extensive experiments, we show that the proposed GANCO framework improves the generalization performance of the original optimization model on various testing distributions with little sacrifice of performance on the original training distribution. Furthermore, we show that the proposed GANCO framework can be readily and effectively applied to other optimization models such as the Policy Optimization with Multiple Optima (POMO, Kwon et al. (2020)).
2
RELATED WORKS
Most deep learning models are trained learn the construction heuristics where the model picks the actions sequentially to construct a solution (e.g., Bello et al. (2017); Nazari et al. (2018); Kool et al.
(2019); Hottung et al. 202T ; Kwon et al. (2020)), which perform well with fairly short running
time. While some other models learn the improvement heuristics to locally refine existing solutions, which usually search over large number of solutions and are relatively slow. Moreover, they often need to fit in frameworks specifically designed for different problems, such as 2-opt (d O Costa et al. 2020), , large neighborhood search (Hottung & Tierney 2020) and combinations of local oper- ators (Lu et al. 2020). Most models are trained with reinforcement learning (RL) except for several ones with supervised learning, e.g., |Vinyals et al. (2015) and Joshi et al. (2019). Though we use representative construction heuristic models with RL in the experiments, our proposed GANCO framework can also be applied to models of other types.
The most well-known models trained with adversary the Generative Adversarial Networks (Goodfellow et al.] 2014 Yang et al.) 2018 Zhang et al. 2019). which serve to generate new data samples to imitate the training set. The generative network generates the sample candidates whereas the discriminative network classifies whether the sample is generated or genuine. In contrast, the goal of our proposed GANCO framework to train the optimization model for better generalization ability where the generation model is used only to generate more informative training samples. The idea of using adversarial training to improve RL robustness has also been studied in other fields such as Atari games and robotics PPinto et al. 2017 Khirodkar& et al., 2018 Dennis et al. (020). However, existing works in this direction are not directly applicable to our task due to unique properties. The key is how to define the adversary, which is specific to the application domain. In the field of COPs, we define the adversary as hard instance generator, which is evaluated by performance gaps of the optimization model with respect to a traditional non-learning bascline algorithm.
To the best of our knowledge, the most related work considering generating data samples for COPs is Liu et al.) (2020) where the samples are generated by performing crossover and mutation to ex- isting instances. The goal is to search better parameters configuration for given traditional solvers. Whereas our proposed framework is designed to generate instances with the guidance of deep rein- forcement learning and improve the generalization performance for neural combinatorial optimiza- tion models. In our experiments, we also verify the necessity of our data generation method.
2

---

Under review as a conference paper at ICLR 2022
(Dke prggca daad
Air Geceration Trakking
Zar Opereiaston Triksiep
2nd Gereratiie Trasking
2nd Operttatee Trasiigg
Saye ang
Ne rp
Oin batessad
ippa
Detazon
Traking bearse
Muce
Trae beascet
Vodd
Thaingg reanees
Open aa
GARCS 063t
Oprerie Maxe
CALLO DeseAss
Quenisze Mice 1e04
GANCO Sarcled
GAROO Sample Fearon
Opansaaie Loo
Gasrácn Loo
Oummaate Loo
Raye Agachin
Figure 1: Generative Adversarial Neural Combinatorial Optimization (GANCO) framework. We use 2 adversarial iterations of generation training and optimization training for illustration purpose.
MODEL
For most learning based methods, the patterns are learned from the training data and usually appli- cable similar testing samples. However, if the distributions of training and testing samples are considerably different, these learned patterns may not be general enough to guarantee desirable in- ference performance. As we will show in the experiments, this issue is particularly severe for COPs due to the intricate relationship between the solution and the instance distribution.
Instead of designing a network architecture to achieve better generalization performance for specific problems, we aim to propose model agnostic framework which is generally applicable to different optimization models and training methods. The only requirement for the optimization models is that they are able to learn effective patterns from the training data and perform well on similar testing samples, which could be fulfilled by most of the recent learning based models.
To this end, we propose the Generative Adversarial Neural Combinatorial Optimization (GANCO) framework, as shown in Figure [ Rather than training the optimization model solely on instances sampled from the predefined training distribution, also deploy another deep learning model to generate instances on which the optimization model performs poorly. The generation model is trained by reinforcement learning maximize the performance gap between the optimization model and a non-learning baseline algorithm on the generated instances. And the optimization model trained with the generated samples to improve the performance words, the generation model and the optimization model are trained to maximize and minimize the performance gaps on the generated instances, respectively. In such an adversarial training way, the lower bound of the optimization model performance on the instance distributions generated by the generation model will be pushed up. We detail the generation model and the GANCO framework in the following subsections.
similar instances. In other
3.1 GENERATION MODEL.
As suggested in existing works (Kool al. 2019 Kwon et al. 2020), many important COPs be viewed as graph of n nodes with different attributes, like the city coordinates for TSP and the item information for KP. Therefore, we formulate the data generation task as determining the attribute values for each node of an instance. However, the proposed framework could be easily adapted to other types of COPs, such by determining the presence of each edge for problems depending on the graph connectivity (e.g., the Boolean Satisfiability Problem).
The generation model f2 takes the noise sample h for each node as the input to output the distribution parameters for the node attributes. We format the noise input h e R=*2 as for each node j = 1,.., n following the unit uniform distribution independently, i.e., h (O, 1). Pertaining to the network architecture, we use the self-attention block proposed in the Attention Model (AM, Kool et al. (2019). which consists of a multi-head self-attention layer (Vaswani et al.) 2017). two node-wise feed- layers with Batch Normalization (loffe & Szegedy (2015) and skip connection (He et al. 2016). The noise input is node-wise linearly projected to H dimeension and encoded by l self-attention blocks. And another node- wise linear layer with sigmoid activation projects the hidden vectors to the output distribution parameters 2(h)= e gn where d is the number of attributes for each node. Then we draw the sample T from the Gaussian distribution N M(,,o*
in -- 2-dimensional variables
3

---

Under review as a conference paper at ICLR 2022
with mean fl Q(h) and fixed standard deviation σ. The network outputs are kept in the same range [o, 1] to use the same variance for different attributes. The sample ă is scaled to the corresponding valid ranges (and discretized for discrete attributes) attain the node attributes x = A()).
The goal of the generation model is to generate instances on which the optimization model currently performs poorly. Since different instances have different optimal objective values, the attained ob- jective values alone are not meaningful enough to evaluate the model performance. Although the optimality gap appears to be good alternative metric in this case, it often requires expensive com- putation to attain the optimal solutions. On the other hand, while achieving approximate solutions, traditional non-learning algorithms tend to perform relatively stably on instances with different dis- tributions, compared to the learning based methods. Therefore, the performance gaps of the opti- mization model with respect to a traditional non-learning baseline algorithm could be regarded as favorable metric. Theoretically, the baseline algorithm performance can be arbitrarily inferior as long as it performs consistently (e.g., similar optimality gaps) on different instances. As we will show in our experiments, the baseline algorithms do not need to be very strong or fast as the training for generation models converges in a relatively small number of iterations.
The generation model is trained by the reinforcement learning (RL). Specifically, the slate of RL environment is the noise input h E R=* The action is to sample the attribute values for a node. An episode is to sample the attribute values z A(z) with 2 >N((h)) for all the nodes to form an instance. However, as the sampled attributes for one node will not affect the other nodes, the episode be viewed as only containing one action with large action space to sample all the node attributes at the same time. The reward for an episode is the performance gap between the optimization model & and baseline algorithm B on the sampled instance x. The loss function is formally defined as follow,
(1) where G(z, 4 B) = (z)(z) - (0()))/O is the performance (objective) gar") Os and Og(œ)) are the objective values of the solutions found by the optimization model t and the baseline algorithm B for the generated instance xr respectively. Different from the generator in GAN (Good- fellow al. (0144) which deterministically infers the instance given the noise input, we sample the noise input to infer the distribution and sample the instance from the output distribution. The gener- ation model is trained by the REINFORCE algorithm (Sutton al., 2000) with reward baseline as
L( -
G(,, B).
the mean of the gaps in a batch. The gradient to train the generation model is expressed as follow,
1 N N
1 N N
VnL(S)) ~
Σ
G(E,, B)
Σ G(aj, 2 B) ValogN (z);))(),)))²)))
(2)
where i and j are the instance indices; N is the batch size; ā; E Raxd ~ N(((h,)), o²); and (a 2(hs), d²) is the probability of 5; sampled from the Gaussian distribution (((()))
3.2 GANCO FRAMEWORK
The formal flow of the GANCO framework is summarized in Algorithm | The GANCO framework compatible with different optimization models and training algorithms. In the framework, the optimization model is always trained by the same algorithm from its original work.
Pretraining Stage First, we train the optimization model on the instances sampled from the original training distribution. To make sure that the performance improvement in the experiments is brought by the proposed GANCO framework rather than more epochs of training, we train the model until fully converged. However, convergence is not necessary in practice.
Adversarial Training Stage After pretraining, the generation model and optimization model are trained alternatively during the adversarial iterations. In each iteration, the generation model is first trained to generate the instance distributions on which the current optimization model exhibits poor performances. And the training distribution will be augmented with the newly generated distribu- tion. Then the optimization model is trained with instances sampled from the augmented distribution to improve the performance new instances while preserving the performance old ones.
Herr we follow the convention to formulate the COPs minimizing the objective functions. The maxi- mization problem can be viewed as minimizing the negative objective.
4

---

Under review as a conference paper at ICLR 2022
Generation Training At the beginning of each adversarial iteration, the parameters of the genera- tion model are re- re-initialized randomly. In doing so, it prevents the model from being stuck in the local optimum of previous adversarial iterations and also allows the model learn diverse instance distributions. Specifically, the generation model is trained using the gradients in Eq. (
Optimization Training In each adversarial iteration, the optimization model is trained with the same algorithm from its original work but on different distributions. To achieve desirable perfor- mance both the base training distributions and the adversarial generated distributions, we main- tain a number of samples from the base distributions while adding the samples from the newly generated ones. In the experiments, we find that good performance could be easily and effectively realized by simple data composition rule. Specifically, we always keep half of the samples from the base training distribution and then equally sample the other half from the generated distribution in each adversarial iteration. For optimization models trained by RI., we sample new instances from these distributions for each epoch following the composition rule above.
Algorithm Generative Adversarial Neural Combinatorial Optimization
Input: Optimization model d, generation model Ω2 the non-learning baseline algorithm B, the base training distribution Do the number of adversarial iterations Na. the number of training iterations Nq for Ω and the number of training epochs No for & in an adversarial iteration, the learning rate 1) and batch size N for f2
Output: Generative adversarial trained optimization model while & not converged do
Pretraining Stage
2: Sample dataset X from Do. train & on dataset X
3: end while
4: Initialize the training distribution D as D.
5: for k, < N, do
> Adversarial Training Stage
6: Randomly initialize the parameters for Ω
7: for kg < 1 to Ng do
b kath Generation Training 8: Sample the noise inputs & E IRNN xxx2, and infer the distribution parameters Q(h)
9: for i to N do
10:
Sample the instances D2 with i; (N4,,, and use + and B solve 2; end for S Ω V
11:
13:
end for
14: Augment D with the distribution generated by Ω
15:
for kip + 1 to No do
k2th Optimization Training Sample dataset X from D following dataset composition rule, and train & on dataset X
17: end for
end for
EXPERIMENTS AND ANALYSIS
We adopt the Attention Model (AM, Kool et al. (219)) effectiveness of our proposed GANCO framework. AM is a widely used strong deep learning model for series of routing problems and other COPs such as the Knapsack Problem. is also used the base model in many other recent works, e.g., Kwon et al. 2020);; Xin et al. 2) Hottung et al.) (202I). As heuristic model that learns construct the solution sequentially, AM requires much less expert knowledge about the problems, especially compared with the region and rule design in Chen & Tian (2019) and the various perturbation operators Lu et (2020). Typically, AM consists of an encoder and decoder, which is trained by the REINFORCE algorithm with a deterministic rollout baseline. With three self-attention blocks, the encoder maps the nodes into embeddings. Based on the attention mechanism with glimpse, the decoder sequentially decides which node to visit at each step. We further improve AM in two ways, i.e., removing the Batch Normalization layers and training the model for more epochs until full convergence. Therefore, the performance of our base model is much better than the original ones reported in Kool et al.) (2019). We discuss the reasons for the changes and the performance improvement with more details in Appendix H
the optimization model to verify the
5

---

Under review as a conference paper at ICLR 2022
Table I: Results of AM and GANCO-AM for TSP on instances with different distributions.
71
20
11
50
71 = 100
Dist.
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Cap
Time
Concorde
3.83
0.00%
4s
5.69
0.00%
39s
7.76
0.00%
142s
Base
AM
3.83
0.14%
0.3s
5.73
0.73%
0.8s
7.93
2.16% %
2.1s
GANCO-AM
3,83
0.14%
0.3s
5.74
0.83%
0.8s
7.94
2.28%
2.1s
Concorde
3.19
0.00%
12s
4.01
0.00%
91x
5.15
0.00%
210s
Cluster
AM
3.21
0.39%
0.3s
4.14
3.07%
0.8s
5.60
8.85%
2.1s
GANCO-AM
3.20
0.27%
0.3s
4.10
2.04%
0.8s
5.46
6.06%
Concorde
2.78
0.00%
15s
3.91
0.00%
78s
5.30
0.00%
183s
Uniform
AM
2.79
0.54%
0.3s
4.04
3.37%
0.8s
5.67
7.12%
2.1s
GANCO-AM
2.78
0.19%
0.3s
3.97
1.45%
0.8s
5,51
3.94%
2.1s
Concorde
2.43
0.00%
21s
2.72
0.00%
152s
3.24
0.00%
1968
Diagonal
AM
2.49
2.29%
0.3s
3.35
23.21%
0.8s
5.22
61.47%
2.1s
GANCO-AM
2,44
0.29%
0.3s
2.78
2.37%
0.8s
3.47
7.39%
2.1s
Concorde
3,40
0.00%
12s
4.45
0.00%
51s
5.70
0.00%
167s
Gaussian
AM
3,41
0.32%
0.3s
4.67
4.86%
0.8s
6.21
9.06%
2.1s
GANCO-AN AM
3,41
0.27%
0.3s
4.54
1.96% %
0.8s
6,10
7.02%
2.1s
Concorde
3,40
0.00%
7s
4,50
0.00%
44s
5.76
0.00%
1558
TSPLIB-S
AM
3,41
0.21%
0.3s
4.58
1.77%
0.8s
6.06
5.27%
2.1s
GANCO-AM
3,41
0.17%
0.3s
4.55
1.26%
0.8s
5.99
4.12%
2.1s
We use AM to solve TSP, CVRP, OP, PCTSP and KP in experiments. The model is trained by the GANCO framework for 20 adversarial iterations, during each of which the generation model is trained for at most 2000 iterations (depending problems) with batch size 100 and attribute stan- dard deviation 0.05, and the optimization model trained for 20 epochs with 256000 instances in each. The hyper-parameters for model architecture and optimizer the same those in Kool et al. (2019). For fast convergence and stable training, we fix the parameters in AM encoder and only train the decoder after the pretraining stage. We leverage Concorde, Hybrid Genetic Search (HGS, Vidal (2200). Compass (Kobeaga et al. 2018), Iterated Local Search (ILS) and Dynamic Programming (DP) for TSP, CVRP, OP, PCTSP and KP, respectively, as the non-learning baseline algorithms for training the generation model. As our GANCO framework is relatively robust to the performance of (non-learning) baseline algorithms, we set the number of non-improvement iterations before termi- nation for HGS as 100 instead of the default 20000 to save training time. Also, exploit faster version of ILS and round the item weights to two decimal places for DP. For a fair comparison, we consider the node attribute ranges of the original training distribution as the valid ones and show the results for the five problems on various distributions of instances within those ranges.
Besides, apply the GANCO framework to another prevailing optimization model, i.e., POMO (Koo et al., 2020) to solve TSP and CVRP, and also present more analysis about our GANCO framework. All our codes will be made available soon.
4.1 TRAVELING SALESMAN PROBLEM
For TSP, the attributes learned by the generation model are the two coordinates for each node. The base training instances are generated uniformly in the unit square, following Kool et al. (2019). We adopt instances following five different distributions as the testing sets to evaluate the generalization
performance. Specifically. (1) Clustered: the nodes are distributed in clusters following [Uchoa al.
(2017); (2) Uniform: the nodes are uniformly sampled in rectangle with random aspect ratios; (3) Diagonal: the nodes are distributed near the diagonal of rectangle; (4) Goussian: the nodes follow the bivariate Gaussian distribution with random correlation coefficients; (5) TSPLIB-S: the nodes are sampled without replacement from a random instance of the TSPLIB (Reinelt) 1991). We scale the instance coordinates to the valid range [0. 1] with the aspect ratio fixed between horizontal and vertical axes so that the objective values of all solutions for an instance will only be scaled by the same constant. More details of data generation for each distribution presented in Appendix
The results of Concorde, AM (with greedy decoding) and GANCO-AM are gathered Table T where we report the average objective values and gaps, and the total time for solving the 10000 test-

---

Under review as a conference paper at ICLR 2022
Table 2: Results of AM and GANCO-AM for CVRP on instances with different distributions.
N1
20
It
50
71
100
Dist.
Method
Obj.
Cap
Time
Obj.
Gap
Time
Obj.
Gap
Time
HGS
6.11
0.00%
0.5h
10.34
0.00%
1.4h
15.57
0.00%
3.2h
Base
AM
6.28
2.74%
0.5s
10.76
4.05%
1.2s
16.38
5.22%
2.8s
GANCO-AM
6.29
2.86%
0.5s
10.78
4.22%
1.2s
16.37
5.16%
2.8s
HGS
5.77
0.00%
0.5h
9.43
0.00%
1,4h
14.03
0.00%
3.9h
Original
AM
5.93
2.83%
0.5s
9.90
5.03%
1.2s
15.05
7.25%
2.7s
GANCO-AM
5.94
3.02%
4.82%
1.2s
14.90
6.18%
HGS
3,55
0.00%
0.2h
5.11
0.00%
1.0h
7.21
0.00%
3.1h
Small
AM
4.08
14.86%
0.5s
5.82
13.87%
1.2s
8.79
21.80%
3.4s
GANCO-AM
3.85
8.55%
0.4s
5.63
10.05%
1.1s
8.27
14.65%
2.6s
HGS
8.84
0.00%
0.6h
15.00
0.00%
1.5h
21.93
0.00%
3.7h
Large
AM
9.11
2.99%
0.5s
15.95
6.34%
1.3s
23.47
7.02%
3.0s
GANCO-AM
9.04
2.17%
0.5s
15.89
5.95%
1.2s
23.29
6.20%
3.0s
HGS
5,93
0.00%
0.4h
9.74
0.00%
1.2h
14.46
0.00%
2.9h
Identical
AM
6.19
4.47%
0.5s
10.25
5.31%
1.1s
15.75
8.93%
3.4s
GANCO-AM
6,12
3,34%
0.5s
10,20
4.75%
1.1s
15.47
7.03%
3.0s
HGS
5,83
0.00%
0.5h
9.56
0.00%
1.4h
14.05
0.00%
3.4h
Quadrant
AM
6.05
3.72%
0.5s
10.24
7.11%
1.1s
15.37
9.40%
3.0s
GANCO-AM
6.04
3.59%
0.5s
10.18
6.52%
1.2s
15.14
7.76%
3.0s
HGS
4.40
0.00%
0.4h
6.69
0.00%
1.3h
9.52
0.00%
3.4h
SL
AM
4.59
4.18%
0.4s
7.17
7.21%
1.1s
10.67
12.06%
3.38
GANCO-AM
4.58
4.05
6.59%
1.1s
10.43
9.51% %
2.8s
ing instances sampled from each distribution, respectively. For the traditional algorithm Concorde, run 20 instances in parallel 28-core CPU (also applies to HGS, Compass, ILS and DP in the subsequent subsections). The AM and GANCO-AM are trained and tested on a RTX-2080Ti GPU. Generally, their time is much shorter than the traditional algorithm indicated in the table(s), which is a core strength of deep models. Clearly, GANCO-AM improves the performance on vari- ous generalization testing sets (i.e., the last five distributions in Table by large margins. While the optimality gaps of AM could be up to 61.47% for TSP100 on certain distribution, its performance after GANCO training tends be much desirable and stable. As the GANCO framework does not change the optimization model architecture or the total number of parameters, the slight drop of performance on the base training distribution fairly acceptable.
A more complete comparison with other methods is presented in Appendix ^ where we show the performance improvement of GANCO-AM over AM while sampling more solution trajectories (e.g., GANCO-AM reduces the average gaps of AM on generalization distributions from 16.52% and 14.55% to 4.47% and 3.48% for TSP100 with 10 and 100 trajectories, respectively). Although we follow the convention in existing works (Kool et al. 2019) to train and test the model fixed-size in- stances (n = 20, 50, 100 for routing problems), we also demonstrate that GANCO-AM significantly improves the results of AM larger-size instances of the TSPLIB benchmark in Appendix B where the average gap is reduced from 11.95% to 7.05% for instances with 100-300 nodes.
4.2 CAPACITATED VEHICLE ROUTING PROBLEM
Following Kool et al. (2019), the base training distribution with respect to the customer and depot coordinates is the same as the one for TSP. The demands are uniformly sampled from (1...,9), and the capacities are fixed as 30, 40, 50 for CVRP with 20, 50, 100 customers, respectively. Therefore, apart from the coordinate attribute, the generation model also learns the demand attribute given the fixed capacities. For the generalization testing sets, the customer nodes follow the six distributions used for TSP (including its base distribution). The depots are distributed uniformly, fixed at the center corner in the unit square, following CVRPLIB (Uchoa et al.) 2017). For the customer de- mands, we adopt six distributions based on CVRPLIB. Particularly, they are sampled from {1..... 9} (Original) or (1,2} (Small) or {8,9) 9} (Large), random yet identical for all nodes within the same instance (Identical), small or large depending on the node quadrant (Quadrant). and most small with few large ones (SI.), respectively. More details for the testing
presented in Appendix C

---

Under review as a conference paper at ICLR 2022
Table Results POMO and GANCO-POMO for CVRPI00.
HGS
Single trajectory
100
trajectories
Dist.
Obj.
Time
Method
Obj.
Gap
Time
Obj.
Gap
Time
POMO
16.09
3.32%
4.7s
15.87
1.97%
51.3s
Base
15.57
3.2h
GANCO-POMO
16.12
3.56%
4.9s
15.89
2.09%
51.6s
POMO
15.14
7.89%
4.0s
14.69
4.68%
58.3s
Original
14.03
3.9h
GANCO-POMO
14.56
3.78%
3.8s
14.35
2.26%
50.8s
POMO
10.15
40.74%
4.1s
8.84
22.47%
61.1s
Small
7.21
3.1h
GANCO-POMO
7.78
7.82%
3.68
7.57
4.91% %
48.0s
POMO
24.22
10.43%
4.5s
23,40
6.68%
68,5s
Large
21.93
3.7h
GANCO-POMO
22.94
4.56%
3.9s
22.58
2.95%
53.8s
POMO
16.28
12.60%
4.5s
15.52
7.38%
67.3s
Identical
14.46
2.9h
GANCO-POMO
14.93
3.28%
4.1s
14.75
2.01% %
54.4s
POMO
15.92
13.32%
4.4s
15.15
7.81%
66.1s
Quadrant
14.05
3.4h
GANCO-POMO
14.78
5.20%
3.8s
14.51
3.24%
53.7s
POMO
10.79
13.28%
4.2s
10.25
7.67%
57.9s
SL
9.52
3.4h
GANCO-POMO
10.05
5.52%
3.7s
9.84
3.35%
49.1s
As shown in Table 2] the proposed GANCO framework ameliorates the AM performance by large margins on almost all generalization testing sets with greedy decoding. However, for CVRP20, the performance of AM and GANCO-AM are close on some testing sets (such as Original, Quadrant and SL), which indicates that the original AM is fairly robust to certain distributions as the problem size small. Appendix C we also compare with another popular traditional algorithm LKH3 [Helsgaun] 2017) and demonstrate the significant improvement of GANCO-AM over AM with the sampling (rather than greedy) version (e.g., the average gaps are reduced from 9.06% and 7.62% to 6.93% and 5.75% for CVRP100 with 10 and 100 trajectories, respectively).
4.3 ORIENTEERING PROBLEM, PRIZE COLLECTING TSP AND 0-1 KNAPSACK PROBLEM
We also apply the GANCO framework AM to solve OP, PCTSP and KP, respectively. The base training distributions for OP and PCTSP are the same as those in Kool et al. (2019). The prizes setting for OP uses the hardest increase with the distance to the depot. The base distribution for KP follows the setting in Kwon al. (2020). More details for problem settings, generalization testing distributions and results presented in Appendix and OP, PCTSP and KP, respectively. GANCO significantly boosts the performance on the three problems of different sizes, with greedy decoding and trajectories sampling for AM, respectively (e.g., with greedy decoding, the average gaps for OP100, PCTSP100 and KP200 are reduced from 13.68% 14.75% and 0.25% 7.67%. 7.33% and 0. 0.1%, respectively).
reported in its original work, where the customer prizes
4.4 POLICY OPTIMIZATION WITH MULTIPLE OPTIMA
To demonstrate that the GANCO framework is model agnostic, further apply the Policy Optimization with Multiple Optima (POMO, Kwon et al. (2020) for solving TSP and CVRP. We only consider 100 nodes since the results of the improved AM in our experiments are superior or close to those of POMO on other sizes reported in K won et al. (020)). In Table 3 we record the results of POMO and GANCO-POMO by inferring a single trajectory and 100 trajectories (with the multi-starting-
strategy) for solving CVRP100, Clearly, the improvement of GANCO-POME over POMO is salient for both decoding methods. In Appendix
G we present more discussion about CVRP and detailed results for TSP100 (the average gaps are reduced from 7.79% to 2.08% with single trajectory, and from 3.64% to 0.90% with 100 trajectories for TSP100, respectively).
4.5 ANALYSIS ON THE GANCO FRAMEWORK
In Figure we plot the objective gaps GANCO models on various testing sets along adversar- ial iterations for TSP or CVRP, where iteration 0 refers the original AM or POMO. To better demonstrate the learning process, we adopt the gaps with respect to the best objective values among all the iterations. Though fluctuating some testing sets especially for the early iterations, the
8

---

Under review as a conference paper at ICLR 2022
6.0%%
38.06
5.00%
25.5%
12.0%
4.00%
20.0%
2,0%
35%
Base
Ouserdd
1.75%
Bage
Drign
Bace
Orignnl
Jofomm
Staal
Shiel
2.5
Oigenal
125%
Large
Large
Gaussan
1.5%
0.75%
0.0%%
2.0%
a.%
0.2%%
0.0%
0.0%%
15
0.0%
10
(a) GANCO-AM on TSPI00
(b) GANCO-AN AM on CVRPI00 (c) GANCO-POMO on CVRP100
Figure Results of models trained with GANCO on testing sets along the adversarial iterations.
performance on those generalization testing sets becomes more desirable and stable quickly as the
iteration increases.
Similarly, in Figure we also plot the objective gaps of GANCO-AM for CVRP100 on 20 distributions, each of which is generated in the respective adversarial iteration. Clearly, the objective gaps of the worst-case instances found by the generation model are decreasing as the
Indox of ganerated eistribution
25%
700%
300%
eration increases, indicating that the lower bound of per- formance is pushed up with our GANCO. Furthermore, even before train the model tion (the diagonal polyline), the performance on it also usually tends to become better, which verified the effec- tiveness of the learned patterns. Besides, we also compare our data generation method with the genetic based one in Liu et al. (2020) to justify the deep RL in our GANCO. The details are presented Appendix A
10
100%
generated distribu-
15
5%
50%
0%
Optimization model Index
Figure 3: GANCO-AM results of CVRPION 100 on distributions generated by the generation model along the 20 ad- versarial iterations.
Though deep learning models still perform relatively in- ferior strong traditional algorithms on well-studied COPs, GANCO framework effectively improves the gen-
cralization ability. With certain settings for the less studied problems, deep models performs favor- PCTSP50. GANCO-AM improves
ably against the traditional ones (e.g.. inferring 10 trajectories the average gaps on testing sets from 2.32% to 1.31% with average run time 8s for 10000 instances, compared the fast ILS 1.67% and 106s). Especially the adversarial training does not alter the model architecture and consumes fairly short time. The hardest training in our methods (GANCO- AM for CVRP100) costs less than days compared to the 14 days for pretraining of AM. Further- more, aiming at improving the generalization ability, GANCO could also be potentially applied to upcoming deep models, e.g., the one has stronger performance and could handle much larger sizes.
To further demonstrate the effectiveness of adversarial training in the proposed GANCO framework, conduct more experiments in Appendix ! We demonstrate that GANCO achieves most of the benefits of training on in-distribution data and achieves better generalization performances com- pared to the model trained with multiple distributions. Furthermore, the generation model tailors distributions bespoke to the specific problem.
CONCLUSION AND FUTURE WORK
In this paper, we propose the GANCO framework improve the generalization ability of Neural Combinatorial Optimization models. Trained by reinforcement learning, a generation model aims to find instances hard for an optimization model. With the two models trained alternatively in an adversarial way, the generalization ability of the optimization model is significantly boosted. We apply GANCO to two optimization models including AM and POMO on various COPs. Extensive experimental results show that GANCO framework ameliorates the generalization performance by large margins with slight performance drops on the original training distribution. In future, we will investigate more optimization models and COPs, and study how tackle much larger instances.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Irwan Bello, Hieu Pham, Quoc Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In International Conference on Learning Representa- tions Workshop, 2017.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 6281-6292, 2019.
Paulo R d Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning. pp. 465-480. PMLR, 2020.
Hanjun Dai, Elias B Khalil, Yuyu Zhang. Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp.
Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. Advances in Neural Information Processing Systems, 33:1 1049-1111,,, 2020.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances neural information processing systems, 27, 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Keld Helsgaun. An effective implementation of the lin-kernighan traveling salesman heuristic. European jourmal of operational research, 126(1):106-13) 130, 2000.
Keld Helsgaun. An extension of the lin-kernighan-helseee helsgaun tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 2017.
André Hottung and Kevin Tiemney Neural large neighborhood search for the capacitated vehicle routing problem. In ECAI 2020, pp. 443-450. IOS Press, 2020.
André Hottung, Bhanu Bhandari, and Kevin Tierney. Learning a latent search space for routing prob- lems using variational autoencoders. In International Conference Learning Representations, 2021.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference machine learning, pp. 448 456. PMLR, 2015.
Chaitanya Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint 1106.0::990000222 2019.
Rawal Khirodkar, Donghyun Yoo, and Kris M Kitani. Vadra: Visual adversarial domain randomiza- tion and augmentation. arXiv preprint arXiv: /8/20094 2018.
Gorka Kobeaga, María Merino, and Jose A Lozano. An efficient evolutionary algorithm for the orienteering problem. Computers & Operations Research, 90:42-50 59, 2018.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
Ycong-Dae Kwon, Jinho Choo, Byoungůp Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
Eugene L Lawler and David E Wood. Branch-and mnddd methods: A survey. Operations research, 14(4):699-719, 1966.
10

---

Under review as a conference paper at ICLR 2022
Shengeai Liu, Ke Tang, and Xin Yao. Generative adversarial construction of parallel portfolios. IEEE transactions on cybernetics, 2020.
Hao Lu, Xingwen Zhang, and Shuang Yang. learning-based iterative method for solving vehicle routing problems. In International Conference on Learning Reprexentations, 2020.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, pp. 105400, 2021.
Mohammadreza Nazari, Afshin Oroojlooy, Martin Takáč, and Lawrence V Snyder. Reinforcement learning for solving the vehicle routing problem. In Proceedings of the 32nd International Con- ference on Neural Information Processing Systems, pp. 9861-9871, 2018.
Lerrel Pinto, James Davidson, and Abhinav Gupta. Supervision via competition: Robot adversaries for learning tasks. In 2017 IEEE International Conference on Robotics and Automation (ICRA), pp. 1601-1608. IEEE, 2017.
Gerhard Reinelt, Tsplib-a traveling salesman problem library. ORSA journal on computing, 3(4): 376-384, 1991.
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in neural informa- fion processing systems, pp. 1057-1063, 2000.
Paolo Toth and Daniele Vigo. The vehicle routing problem. SIAM, 2002.
Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3):845-858, 2017.
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, pp. 5998-6008, 2017.
Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap neigh- borhood. arXiv preprint arXiv:2012.10388 2020.
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 14x611-624 1-644, 2012.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in Neural Infor- mation Processing Systems, 28:2692-2700,, 2015.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embed- ding glimpse for solving vehicle routing problems. Proceedings of 35th AAAI Conference on Artificial Intelligence, 2021.
Zhen Yang, Wei Chen, Feng Wang, and Bo Xu. Generative adversarial training for neural machine translation. Neurocomputing, 321:146-155, 2018.
Han Zhang, Ian Goodfellow, Dimitris Metaxas, and Augustus Odena. Self-attention generative adversarial networks. In International conference on machine learning, pp. 7354-7363 PMLR, 2019.
A AM EXPERIMENTS ON TSP
For the Traveling Salesman Problem (TSP), the base training instances generated uniformly in the unit square (Kool et al., 2019). We adopt instances following five different distributions as the testing sets to evaluate the generalization performance.

---

Under review as a conference paper at ICLR 2022
1. Clustered: Following Uchha et al. (017), the nodes are distributed in clusters where the number of clusters S is uniformly sampled from the integers (3....8). With the unit square discretized to 1000 x 1000 grid, the cluster centers uniformly and in- dependently sampled. A node is located at location p with probability proportional to s) /0.04) where s is the cluster index and w(p, s) is the distance be- tween location p and cluster center s. All nodes in an instance are located at distinct points in the grid.
Ex
2. Uniform: For each instance, the nodes are distributed uniformly in rectangle. The aspect ratio of the rectangle is sampled from the uniform distribution U(0, 1) and the longer side is the horizontal or vertical axis with equal probabilities.
3. Diagonal: The nodes are distributed along the diagonal of a rectangle. For each instance, rectangle is generated in the same way in Uniform and noise size t is sampled from the uniform distribution (0.05, 0.2). One of the two diagonals is selected with equal probabilities. For each node in this instance, one point is sampled uniformly from the selected diagonal. And two noises independently sampled from the uniform distribution t-),tt) are imposed for the horizontal and vertical axes, respectively. to attain the node coordinates.
4. Gaussian: For each instance, correlation coefficient p is sampled from the uniform dis- tribution U(0, 1). The nodes follow the bivariate Gaussian distribution with the mean (0.5, 0.5), the standard deviation for both axes, and the correlation coefficient p. How- ever, we will scale the instance coordinates to the valid coordinate range [0, 1]. Therefore, the mean and standard deviation will not affect the scaled instance.
5. TSPLIB-S: For each instance, a reference instance is sampled from the TSPLIB benchmark (Reineli 1991). The nodes are sampled from this reference instance without replacement to form a new instance. We sample the instances in this way to have fixed number of nodes for testing set. However, we further present the results on the TSPLIB benchmark with various sizes in Appendix B
We do not include the Random-Cluste nodes are distributed uniformly in the unit square and the other half are distributed in 3-8 clusters. It is similar to the base unit uniform distribution for problems with 100 nodes or less.
node distribution in Uchoa et al. (017)) where half of the
In Table we show the results of Concorde, LKH, original AM and GANCO-AM on the testing sets with different instance distributions, which include the base training distribution and 5 generalization testing distributions. Concorde is highly optimized exact solver for TSP, which finds the optimal solutions in fairly short time. LKH (Helsgaun) 2000) uses the same hyper- prree-pprameters (10000 trails and 10 runs) as those in Kool et al. (2019). For all the traditional algorithms (Concorde and LKH for TSP, HGS and LKH3 for CVRP, Compass for OP, ILS for PCTSP, DP for KP). we run 20 instances in parallel on a 28-core CPU. And the run time of AM and GANCO-AM is measured on a single RTX2080Ti GPU. In addition to the greedy decoding version of AM and GANCO-AM which infer one solution trajectory, we further include another two versions, i.c., inferring 10 trajectories (10t) and 100 trajectories (100t). In the greedy version, the node visit each step is selected as the one with the highest probability. More solution trajectories could be achieved by sampling the node to visit each step for multiple times according to the inferred probability. With one solution trajectory greedily inferred, we further sample another 9 and 99 solution trajectories which lead to versions of 10 trajectories (10t) and 100 trajectories (100t), respectively. Clearly, for most settings, GANCO-AM improves the performance of the original AM by large margins. For small problem sizes (n 20), some distributions (Gaussian and TSPLIB-S) are not significantly different from the base one, where the performance of AM and GANCO-AM is similar. For the base training distribution, the performance of GANCO-AM is fairly close to the original AM. As the GANCO framework does not change the model architecture the total number of parameters, the small performance drop on the original training distribution is acceptable considering the improvement of generalization ability on other testing distributions.
To demonstrate the necessity of deep generation model trained by reinforcement learning in GANCO, we adopt the genetic based (GB) generation method in Liu al. (2020) our framework, namely GB-AM. Instead of managing instance distributions in GANCO, GB applies crossover and mutation operators to given instances for generating new ones. After the pretraining stage, GB first
12

---

Under review as a conference paper at ICLR 2022
Table Results of AM and GANCO-AM for TSP on instances with different distributions.
20
100
Dist.
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
Conzorde
3.83
0.00%
4s
5.69
0.00%
39c
7.76
0.00%
142s
LKH
3.83
0.00%
32s
5.69
0.00%
2966
7.76
0.00%
1241s
AM greedy
3.83
0.14%
0.3s
5.73
0.73%
0.85
7.93
2. 161
2.18
GANCO-AN A.M greedy
3.83
0.3s
7.94
2.28%
GB-AM greedy
3.83
0.12%
0.3s
5.73
0.71 %
0.8s
7.91
1.97%
2.18
Base
AM 10E
3.83
0.07%
2s
5.71
0.43%
7.88
1.50%
20s
GANCO AM 10:
3.83
0.08%
2s
5.72
0.49%
7.88
1.57%
20s
GR-AM 10c
3.83
0.07%
24
5.71
0.40%
76
7.86
1.34%
20s
AM 100x
3.83
0.04%
5.70
0.26%
74s
7.84
1.08%
2066
GANCO-AM 100%
3.83
0.05%
25s
5.71
0.32%
74s
7.85
1.13%
2066
GB-AM
3,83
0.04%
5.70
74s
7.83
0.96%
2066
Concorde
3.19
0.00%
12s
4.01
0.00%
91s
5.15
0.00%
210s
LKH
3.19
0.00%
110s
4.01
0.00%
655s
5.15
0.00%
2754s
AM greedy
3.21
0.39%
0.3s
3.07%
5.60
8.85%
GANCO-AM greedy
3.20
0.27%
0.3s
4,10
2.04%
0.85
5.46
6.06%
2.18
GB gready
3.21
0.40%
0.3s
Cluster
AM 10h
3.20
0,20%
2s
4.09
1.99%
76
5.53
7.43%
201s
GANCO-AM 10t
3,20
0.14%
2s
4.06
1.25%
5.39
4.64%
20s
GB-AM 10k
3.20
0,22%
28
4.10
2.11%
5.57
8.24%
20s
AM TOXt
3.20
0.12%
25s
4.07
1.31%
77s
5,46
6.04%
208s
GANCO-AM 100k
3.20
0.09%
77s
3.58%
GB-AM AM 1001
3.20
0.12%
2.5
4.07
1.42%
77%
5,50
6.85%
208s
Concorde
2.78
0.00%
15s
3.91
0.00%
78s
5.30
0.007%
1833
LKII
2.78
0.00%
111s
3.91
0.00%
712x
5.30
0.00%
20515 1
AM greedy
2.79
0.54%
0.36
4.04
3.37%
0.85
5.67
1.12%
2.15
GANCO-AM greedy
2,78
0.19%
0.3s
1.45%
GB-AM greedy
2.79
0.53%
0.3s
4.12
5.25%
0.8s
5.67
7.06%
2. 2.15
Uniform
AM T0t
2.78
0.28%
25
4.00
2.13%
21s
GANCO-AM 10t
2.78
0.10%
28
3,95
0.83%
76
5.45
2.97 %
216
GB-AM 10x
2.78
0.26%
2s
4.05
3.54%
5.61
5.96%
21s
AM IOX
2.78
0.15%
26s
3.97
1.43%
77%
5,56
4.97%
2088
GANCO-AM 100s
2.78
0.05%
26s
3.93
0.51 %
77%
5.42
2.26
208s
GB-AM
2.78
0.14%
77s
5.56
Concorde
2.43
0.00%
21s
2.72
0.00%
152s
3.24
0.00%
196s
LKHI
2,43
0.00%
472s
2.72
0.00%
1775s
3.24
0.01%
3371
AM greedl
2.49
2.29%
0.3%
3.35
23.21%
0.86
5.22
61.47%
2.18
GANCO-AM greedy
2.44
0.29%
0.3s
2.78
2.37%
0.8s
3.47
7.39%
2. ls
GB-AM greedy
2.48
1.90%
0.3s
3.66
34.72%
78.76%
2.18
Diagonal
AM IUI
2.45
1.10%
28
3.17
16.68%
78
5,08
56.92%
20s
GANCO-AM 10t
2.44
0.13%
2s
2.76
1.47%
3.44
6.25%
20s
GB-AM 10k
2,46
0.96%
28
3,26
19.89%
5.61
73.51%
20s
AM I0X
2.45
0.62%
26s
3.04
11.95%
77%
4,39
51.19%
209
GANCO-AM 100k
2,43
0.06%
26s
2.74
0.88%
776
3.40
5.05%
209
GB-AM 100t
2.45
0.53%
26s
3.06
12.65%
77s
5,34
65 02%
209
Concorde
3.40
0.00%
51s
LKH
3.40
0.00%
75s
4.45
0.00%
4218
5.70
0.00%
1335s
AM greedy
3.41
0.32%
0.334
4.67
4.36%
0.88
6.21
9.06%
2.15
GANCO-AM greedy
3.41
0.27%
0.3s
4.54
1.96%
0.8s
6.10
7.02%
2.
GB-AM greedy
3.41
0,36%
0.3s
4.65
4,30%
0.8s
6.25
9. 9.69%
2.18
Gaussian
AM 10L
28
7.92%
20s
GANCO AM 10:
3.41
0.15%
2%
4,51
1.22%
7s
6.01
5.54%
20s
GR-AM
3.41
0.
24
2.99%
20s
AM IOX
3.40
6.08%
26s
4,56
2.34%%
17%
6.09
6.917%
209
GANCO-AM 100k
3.40
10%
26s
4.49
0.79%
77%
5.95
4.33%
209
GB-AM 100r
3,40
0.10%
4.55
2.09%
77s
6.14
7.84%
209s
Concorde
3.40
0.00%
7s
4,50
0.00%
44x
5.76
0.00%
155s
3.40
0.00%
4.50
0.01%
5.76
1386s
AM greedy
3.41
0,21%
0.3s
4.58
1.77%
0.8s
6.06
5.27%
2.18
GANCO-AM greedl
3.41
0.17%
0.3s
4.55
1.26
0.8%
5,99
4.12%
2.15
GB-AM greedy
3.41
0.21%
0.3s
4.58
1.77%
0.8s
6.09
5.79%
2.18
TSPLIB-S
AM 10:
3.40
0.11%
28
4.55
1.23%
78
6.U1
4,33%
21s
GANCO
0.10%
2%
21s
GR-AM 10c
3.40
0.11%
24
4.55
1.24%
76
6.04
4.88%
21s
AM
3,40
0.06%
4.54
0.89%
775
5.97
3.03%
2108
GANCO-AM 100t
3.40
0.06%
26s
4.52
0.50%
77s
5.88
2.18%
210s
GB-AM 1001
3.40
0.06%
26s
4.54
0.91%
77%
6.00
4.16%
210s
samples a dataset from the base training distribution. During the adversarial training stage, GB generates each new instance with the crossover and mutation operators. Two reference instances are randomly selected from the dataset. The ith node attributes (coordinates) are taken from the corresponding node of either reference instance with equal probability. And then each coordinate is
13

---

Under review as a conference paper at ICLR 2022
mutated with probability 1/vn be replaced with random number sampled from the unit uniform distribution (n is the number of nodes). And same as GANCO, the objective gaps of the optimiza- tion model with respect to the baseline algorithm (Concorde) are used as the score for the instances. Given the objective gap scores, a binary tournament is used to remove an instance with lower score (since we plan to reserve the hard instances) and keep the dataset size unchanged. The genetic based generation is performed at the beginning of each adversarial iteration and the optimization model trained on the new dataset. For fair comparison, we use the same hyperparameters (number of adversarial iterations, number of running for the baseline algorithm, number of epochs for training the optimization model and number of instances in an epoch) for GB as those for GANCO.
As shown in Table GB-AM does not improve the performance of AM on the generalization testing distributions. However, the performance on the base training distribution is slightly boosted. This result is expected because the genetic based generation method tends to search locally within the field of base training distribution to find the hard instances. The resulting distribution still approxi- mately follows the base training distribution. It would be extremely hard for the genetic operators to attain instances following a significantly different distribution. If we discretize the node attributes, the generation task for finding instances with large objective gaps is essentially Combinatorial Op- timization Problem. Therefore, to tackle such a relatively hard task, we exploit a deep model trained with reinforcement learning, which is fairly effective
have demonstrated in the experiments.
B AM EXPERIMENTS ON TSPLIB
In Table 5 we show the greedy decoding results of AM and GANCO-AM on TSPLIB instances with 100-1000 nodes. Both models are trained only with instances of 100 nodes. The instance coordinates are scaled to the valid range [0, 1] with the fixed aspect ratio between the horizontal and vertical axes. Therefore, the objective values of the tours for an instance are scaled by the same constant. As the models are trained for 2-dimensional Euclidean TSP, we treat all the instances as in this distance space. Even though both models are trained with fixed-size graphs of 100 nodes, the performance on medium-size instances with 100-300 nodes are reasonably good. The average objective gaps for AM and GANCO-AM are 11.5%% and 7.05% on instances with 100-300 nodes. Clearly, GANCO-AM effectively improves the generalization performance. However, both models start to deteriorate with lager sizes. The average gaps for AM and GANCO-AM are 27.44% and 23.37% on large instances with 1000 nodes. Nevertheless, the GANCO-AM still improves the generalization performance over AM.
C AM EXPERIMENTS ON CVRP
We detail the instance distributions for CVRP. The base training distribution is acquired from Kool jet al. (2019). where the coordinates of customers and depot follow the unit uniform distribution, and the demands are uniformly sampled from the integers {1. (1....9) 9}. The capacity is fixed as 30, 40 and 50 for CVRP with 20, 50 and 100 nodes, respectively. Existing benchmarks such as CVRPLIB (Uchoa et al.) 2017) have ranges of node attributes (demands and capacity) different from those of the base training distribution (the valid attribute ranges). Therefore, we use the following testing dis- tributions based on the CVRPLIB benchmark. For all the generalization testing sets, the coordinates of customer nodes follow one of the 6 distributions for TSP (including the base training distribution and generalization testing distributions) with equal probabilities. And the depot follows one of the 3 positioning with equal probabilities, 1) Central: at the center of unit square (0.5, 0.5), 2) Eccentric: at one of the four corners in the unit square, 3) Random: uniformly sampled from the unit square. The capacity is the same constant as the base training distribution. The demand distributions are adapted from the CVRPLIB, and presented as follows,
1. Original: The demands are uniformly sampled from {1,
2. Small: The demands are sampled from the small integers {1, 2}.
3. Large: The demands are sampled from the large integers {8, 9).
4. Identical: The demands for the nodes in the same instance are an identical integer uniformly sampled from (I...99..
14

---

Under review as a conference paper at ICLR 2022
Table Results of AM and GANCO-AM for TSP on TSPLIB instances.
GANCO-AM
GANCO-AM
Instance
Opt.
Obj.
Gap
Obj.
Gap
Iostance
Opt
Obj.
Gap
Obj.
Gap
KroA100
5.41
5.60
3.58%
5.57
2.94%
KroBton
5.63
5.88
4.45%
5.83
3.68%
KroC100
5.29
5.54
4.72%
5.39
1.8%
KroD100
5.46
5.58
2.09%
5.62
2.98%
KroE100
5.62
5,91
5.08%
5,91
5.01 %
rd100
8.07
8.32
3.20%
8,31
3.07%
eil101
2.58%
3.31%
lin105
7.64%
pr107
5.37
5.57
1.71%
5.50
2,46%
pr124
6.26
6.44
2.90%
6.43
2.59%
bier127
6.94
7.55
8.84%
7.30
5.16%
ch130
8.83
9.20
4.14%
9.14
3.47 %
pr136
8.54
8.84
3.45%
8.74
2.33%
grl37*
5.68
6.19
8.97%
6.00
5.57 %
pr144
5.36
5.51
2.75%
5.59
4.34%
kroB 150
6.66
6.95
4.36%
6.89
3.46 %
kroA150
6.71
6.96
6.93
3.23%
ch150
9.34
9.72
4.08%
9.59
2.70%
pr152
5.37
6,02
12.05%
5.73
6.73%
u159
8.09
8.72
7.80%
8,30
2.63%
8,08
9.12
5.04
kroA200
7.45
7.91
6.09%
8.05
8.08%
kroB200
7.47
7.9.
6.20%
7.99
6.98%
gr2024
4.78
7.31
52.79%
5.36
12.13%
l225
10.55
10.98
4.05 %
11.21
6.23%
ssp225
8.22
9.09
10.62%
9.06
10.28%
pr226
5.54
5.76
3.94%
5.80
4.66%
gr229
4.63
9.04
95 43%
5.81
25.52%
gil262
12.05
12.58
4.42%
12.66
5.08%
pr264
9.24
14.84%
12.78%
pr299
7.22
8.16
13.09 %
8.18
13.36%
linhp318
10.17
11.09
9.09%
11.14
9,54%
11.14
n3400
1417
6.29
8,28
31.66%
7,05
12.12%
gr431*
5,45
9.39
72.38%
7.45
36.83%
pr439
8.99
10.72
19.27 %
11.39
26.73%
pob442
13.36
15.58
16.61%
15.19
13.68 %
d493
9.35
12.51
33.75%
11,48
22.80%
an132
10.09
12.61
24.98%
12.62
25.06%
ali535
6.00
8.33
38.87%
8.02
33.57%
u574
12.02
14.71
22.34%
14.67
21.98%
22.36%
p654
9.71
d657
12.21
15.30
25.27%
14.96
22.50%
gr666*
8.74
11.65
33.32
11.65
33.26%
27.91%
31.91%
ds,1000
15,36
20.70
34.72%
20,06
30.59%
The gr ali535 instances treated Fuclidean space
longitude as coordinates.
5. Quadrant: The demands depend on the quadrant of nodes. With the center of unit square (0.5, 0.5) as the origin, the demands of nodes in even quadrants are sampled from small in- tegers (1,2) while the demands of nodes in odd quadrants are sampled from large integers {8, 9}.
6. SL: Most nodes have small demands while other nodes have large ones. For one instance, a random percentage p is sampled from the uniform distribution U (70%, 95%). Thus, p of the total nodes have demands sampled from the small integers {1,2) and the others have demands sampled from the large integers {8.9).
In Table we show the results of HGS, a faster version of HGS, LKH3, the original AM and GANCO-AM AM on the various instance distributions. Hybrid Genetic Search (HGS, Vidal et al. (2012); Vidal (020h) combines genetic algorithm with local search, which is considered as the state-of-the-an algorithm for CVRP. The faster version of HGS (HGS fast) uses the number of non- improvement iterations before termination as 100 instead of the default 20000 for HGS. HGS fast is the non-learning baseline algorithm which we use to train the generation model. LKH3 (Helsgaun) 2017) is an extension of LKH (Helsgaun) 2000) to solve various routing problems including CVRP. We the same papper-prramtterr (SPECIAL parameters, 10000 trials, run) those used in Kool et al. (2199) For distributions with small demands (Small) where the number of nodes in a route large, LKH3 excels at the tour optimization within the route and outperforms HGS. However, LKH3 is unfriendly to the instances with many large-demand nodes. For these distributions (Large, Identical, Quadrant), L.KH3 cannot find feasible solutions for some instances within 10000 trails.
We report the results of AM and GANCO-AM with greedy inferring. 10 trajectories (10t) and 100 trajectories (100t), respectively. As shown in Table 6 the GANCO-AM framework significantly improves the generalization performance over AM on most generalization testing settings. For small size (n = 20), GANCO-AM and AM exhibit similar performance on some distributions (Quadrant and SL), suggesting that AM is relatively robust to these distributions. And the improvement of GANCO-AM on all the generalization testing settings with relatively larger sizes (n = 50, 100) is significant.
15

---

Under review as a conference paper at ICLR 2022
Table 6: Results of AM and GANCO-AM for CVRP on instances with different distributions.
20
1
100
Dist.
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
HGS
6.11
0.00%
1803s
10.34
0.00%
5043s
15.57
0.00%
16866
HGS fast
6.12
0.03%
14s
10.35
0.10%
52s
15.69
0.80%
153s
LKH3
6.12
0.07%
3336s
10.35
0.10%
13223s
15.65
0.54%
24393s
greedy
6.28
2.74%
0.5x
10.76
4.05%
1.2s
16.38
5.22%
2.8%
Base
GANCO-AM greeddl
6.29
2.86%
0.5s
10.78
4.22%
1.2s
16.37
5.16%
2.8s
AM 10L
6.23
1.87%
3s
10.64
2.84%
10s
16.18
3.92%
25%
GANCO. AM 10t
6.23
1.92%
10.64
2.90%
16.17
3.87%
25%
AM T0Ox
6,20
1.36%
40s
10.57
2.18%
107s
16.06
3. 14%
2656
GANCO-AM 109t
6.20
1.41%
40s
10:57
2.18%
109s
16.05
3.11%
268s
HGS
5.77
0.00%
1775s
9.43
0.00%
4926s
14.03
0.00%
1
HGS fast
5.77
0.05%
14s
9.44
0.11%
51s
14.12
0.65%
155s
LKH3
5.77
0.07%
3498s
9.44
0.07%
14042s
14.08
0.33%
29169s
AM greedy
5,93
2.83%
0.3s
9.50
5.03%
1.2s
13.05
7.255%
2.78
Original
GANCO-AM groedy
3.02%
0.5s
4.82%
14.90
6.18%
AM TUE
5.87
1.81%
36
9.76
3.53%
10s
14,86
5.899%
268
GANCO.AM
3,30%
14.71
4.84%
26%
AM TOO
5.84
1.25%
40s
9.68
2.66%
1TTs
14.72
4.89%
272s
GANCO-AM 109t
5.85
1.34%
40s
9.66
2.44%
111s
14.59
3.96%
268s
HGS
0.10%
7.21
0.01%
11073s
IGGS fast
3,55
0.
10%
11s
5.12
0.31
40s
7.25
0.53%
146s
L.KH
3.55
5.10
0.00%
7:21
0.00%
43666
AM preedy
4.08
14.98%
0.3s
5.82
14.08%
1.2s
8.79
21 82%
3,46
Small
GANCO-AM groedy
3.85
8.67%
0.4s
5.63
10.26%
1.1s
8.27
14.66%
2. 2.68
AM TÚL
3.91
10.23%
5.62
10.21%
10s
8.48
17.52%
31%
GANCO-AM 10t
3.74
5.59%
36
5.46
6.94%
96
8.08
11.97%
26s
100K
7.18%
38s
1146
8.27
14.39%
GANCO AM 109t
3.69
3.96%
36s
5.36
4.94%
102s
7.93
9.97%
261s
HGS
8.84
0.00%
2031s
15.00
0.00%
5416s
21.93
0.007
13298s
IGS fast
8.84
0.00%
16s
15.02
0.12%
55s
22.03
0.43%
149
LKH3
AM greedy
2.99%
0.5s
15:95
6.34%
1.3s
23,47
7.02%
3.0s
Large
GANCO-AM
greedy greedy
9.04
2.17%
0.5s
15.89
5.95%
1.28
23.29
6.20%
3.08
8.98
1.36%
15.74
4.97%
23.23
5.91%
28s
GANCO-AM 10t
8.95
1.20%
46
15.68
4.56%
11s
23.02
4.93%
28s
AM 10L
8.92
0.82%
44s
15.58
3.86%
119%
23,03
4.97%
284s
GANCO-AM 10%
8,91
0.71%
43x
15.52
3.49%
120%
22.81
4.01%
28
HGS
5.93
0.00%
1495s
9.74
0.00%
4341s
14,46
0.01%
10521s
HGG fast
13s
9.74
14.49
0.25%
LKH3
AM greedy
6.19
4,47%
0.3s
10:25
5.31%
1.1s
15.75
8.93%
3.44
Iilettiaal
GANCO-AM preedy
6.12
3.34%
0.5s
10.20
4.75%
1.1s
15.47
7.03%
3.0s
AM T0t
6.10
2.91%
46
10.14
4.15%
116
13.55
7.39%
30s
GANCO-AM 10t
2.29%
10.09
3.60%
15.32
5.98%
29s
AM TOX
6.05
2.10%
43s
10.06
3.36%
120%
15.41
6.63%
301s
GANCO-AM
6.03
42x
10.01
119
15.20
5.18%
HGS
5,83
0.00%
1708s
9.56
0.00%
5049s
14.05
0.00%
12235s
HGS fast
5.83
0.04%
14s
9.57
0.10%
50s
14.12
0.48%
152s
LKH3
AM greedy
6.05
3.72%
0.3s
10:24
7.11%
L.1s
15.37
9.40%%
3.0%
Quadront
GANCO-AM greedy
6.04
3.59%
0.5s
1.28
15.14
7.76%
AM LÜt
5.97
2.40%
46
10.08
5,46%
10s
15.13
7.71%
29s
GANCO-AM 10t
5.97
2.34%
4s
10.03
4.89%
11s
14.93
6.25 %
28s
AM T00x
3.93
1.67%
42s
9.97
4.31%
117s
14.36
6.30%
2845
GANCO-AM 109t
5.93
1666%
42s
9.92
3.79%
117s
14.77
5.12%
280s
HGS
4,40
1386s
6.09
0.00%
4601s
9.52
0.00%
12151s
HGS fast
4,40
0.09%
13s
6.69
0.09%
46s
9.56
0.36%
145s
LKHB
4.40
0.00%
1069s
6.69
0.00%
5630s
9.54
0.18%
12595s
AM greedy
4.59
4.24%
0.4%
7.17
7.21%
L.Ts
10.67
12.00%
3.3%
SL
GANCO-AM greedy greedyy
4.58
4.11%
0.4s
7.13
6.59%
1.1s
10.43
9.51
2.8s
2.65%
7,03
5.19%
10.45
9.733%
28%
GANCO-AM 10:
4,52
2.68% %
3s
6.98
4.49%
9%
10.25
7.60%
26s
TOX
4.48
1.89%
38s
6.95
3.93%
10%
10.30
8.13%
271s
GANCO-AM 109
4.48
1.90%
38s
6.90
3.27%
107s
10.12
6.30%
258s
D AM EXPERIMENTS ON OP
In the Orienteering Problem (OP), the vehicle starts from the depot, visits some of the customers and returns to the depot. The goal is to maximize the total prize collected from the customers with the tour distance shorter than the maximum length. We use the hardest setting reported in Kool et al. 2019), where the prize of node increases with the distance the depot. The base training distribu-
16

---

Under review as a conference paper at ICLR 2022
Table 7: Results of AM and GANCO-AM for OP on instances with different distributions.
YI
70
100
Dist.
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
Compass
5.38
0.00%
49s
16.19
0.00%
167s
33.18
0.00S:
454s
AM greedy
5.27
1.96%
0.3s
15.82
2.27%
0.8s
32.40
2.34%
1.7s
GANCO-AM greedy
5.28
189%
0.3s
15.77
2.57%
0.8s
32.30
2.64%
1.7s
Base
15.98
1.33%
32.74
1.32%
GANCO-AM 10t
5.31
I.17%
2s
15.95
1.48%
66
32.69
1.48%
15s
AM 1001
5.33
0.81%
278
16.06
0.81% %
67s
32.92
0.77 %
165s
GANCO-AM 1001
5.34
0.71%
27%
16.04
0.91%
67s
32.89
0.86%
166s
Compass
6.57
0.00%
73s
23.14
0.007
7866
51.23
0.00S
21738
greedy
7.17%
13.74%
2.3s
GANCO-AM gready
6.42
2.22%
0.3s
21.73
6.10%
0.9%
46.67
8.91 %
2.3x
Clustered
AM
6.46
1.62%
21.91
5.33%
88
45.38
11.43%
218
GANCO-AM 10c
6.47
L40%
22.15
4.29%
8s
47.48
7.32%
228
AM 100t
6.49
1.10%
32s
22.18
4. 14%
87s
46.16
9.90%%
221s
GANCO-AM 100t
6.51
0.90%
32s
3.21%
88s
48.08
6.16%
227s
Compass
7.31
0.00%
90s
22.46
0.00%
304s
45.97
0.00%
559s
AM greedy
7.06
3.41%
0.3s
21.40
4.72%
0.9s
41.72
9.26%
2.4s
GANCO-AM greedy
7.11
2.74%
0.3s
21.57
3.97%
1,0s
43.29
5.84%
2.45
Uniform
AM T0X
7.15
2.20%%
36
21.74
3.227%
8s
42.54
7.46%
2.5
GANCO-AM 10t
7.19
2.57%
4.43%
AM 1001
7.20
1.54%
336
21.95
2.30%%
91s
43.07
6.32%
241s
GANCO-AM 100
7.24
33s
22.06
91s
44.37
3.48%
241s
Compass
7.57
0.00%
137x
26.52
0.00%
752s
55.33
0.005
634s
AM greedy
7.28
3.84%
0.3s
24.60
7.24%
1.0s
44.61
19.39%
2.5g
GANCO-AM groody
7.36
2.75%
25.26
4.78%
1.0s
51.37
7.17%
2.4s
Diagonal
AM I0X
7.37
2.645%
36
25.13
3.17%
86
46.35
16.24%
236
GANCO-AM
7.43
1.80%
25.62
3.41%
51.95
6.12%
236
AM 100t
7.42
1.98%
338
25.53
3.76%
915
47.31
14.49%
239s
GANCO-AM 1001
7.48
1.24%
338
25.87
%
91s
52.49
5.15%
240s
Compass
6.14
0.00%
646
19.52
0.00%
40.73
0.00%
927s
AM greedy
5.99
2.51%
0.38
18.48
5.35%
1.0s
35.10
13.68%
2.4s
GANCO-AM greedy
6.00
18.56
4.93%
8.40%
Gaussian
AM 10t
6.05
I.59%
36
18.81
3.66%
8s
35,96
11.71%
22s
GANCO-AM 10t
6.06
143%
36
18.88
3.31 %
8s
37.97
6,80 %
236
AM TOO1
6.08
1.09%
325
19,00
2.697%
901
36.37
10.22%
2M5
GANCO-AM 100t
6.09
0.93%
32s
19.05
2.40%
90s
38.44
5.68%
238s
Compass
20.47
0.00%
857s
AM greedy
6.01
2. 10%
0.3s
19.37
5.37%
1.0s
39
12.32%
2.3x
GANCO-AN A-AM greedy
6.02
1.95%
0.3s
19.50
4.74%
0.9s
41.37
8.03%
2.4%
T
AM TÜ
6.016
1,88%
3r
19,09
3.795%
8s
40.58
9.305
23%
GANCO-AM 10t
6.07
1.22%
36
19.80
3,29%
96
42.29
5.99 %
236
1001
6.09
32s
2.90%
90s
8.32%
232s
GANCO AMM 1001
6.09
0.79%
338
19.97
2.43%
92.
42.79
4.87 %
238s
tion the unit uniform distribution for the node coordinate. The maximum tour length is fixed as 2, 3 and 4 for OP with 20, 50 and 100 customers, respectively. The prize p: of node is determined win J. where Woz is the distance between depot and node i. Therefore,
by p; 100 1 + 99 X maz"" Way
the generation model only learns the node coordinates. For the generalization testing distributions, we use the same coordinate distributions for TSP (Clustered, Uniform, Diagonal, Gaussian and TSPLIB-S) as the ones for the customers. In each generalization distribution, the depot coordinates follow the 3 depot positioning (Centrul, Eccentric, Random) with equal probabilities.
In Table 7 we report the results of Compass Kobeaga et al. 2018), AM and GANCO-AM on the testing distributions for OP. Different from most other routing problems, the objective value is the total collected prize which is to be maximized instead of minimized. The results confirm that the GANCO framework significantly improves the performance on all the generalization settings with different testing distributions, graph sizes and numbers of solution trajectories.
E AM EXPERIMENTS ON PCTSP
In Prize Collecting TSP (PCTSP), the vehicle starts from the depot, visits some of the customers to collect prize and returns to the depot. With the total collected prize no less than a minimum value, the goal is to minimize the tour distance plus the total penalties of unvisited nodes. In Kool et al. (2019). the base training distribution is that the coordinates of depot and customers follow the unit uniform distribution. The prizes are designed to force the vehicle to visit approximately
17

---

Under review as a conference paper at ICLR 2022
Table 8: Results of AM and GANCO-AM for PCTSP on instances with different distributions.
50
Dist.
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
S
3.15
0.00%
862s
4.50
0.00%
6895s
5.98
0.00%
47404s
ILS fast
3.19
1.10%
78s
4.57
1.56%
119s
6.10
2.12%
358s
AM greedy
3.15
0.11%
0.3s
4.54
0.94%
0.76
6.11
2.15%
1.75
GANCO-AM greedy
3.15
0.09%
0.3s
0.90%
2,09%
1.7s
Bose
AM TOI
3.15
-0.19%
36
4.51
0.36 %
75
6.06
1.33%
I6s
GANCO-AM 101
3.14
-0.20%
36
4.51
0.38%
7s
6.05
1.29%
16s
AM TOMN
3.14
+0.37%
32%
4.50
0,088 %
74k
6.03
0.85%
1688
GANCO-AM 100r
3.14
-0.36%
33s
4.50
0.10%
75s
6.03
0.83%
174g
ILS
2,90
0.00%%
3.72
0
9957s
0.00%
57305s
S fast
2.93
1.04%
81s
3.79
1.94%
102s
4.77
2.74%
476s
AM greedy
2,90
0.14%
0.3s
3.79
2.00%
0.9s
5.09
9.53%
2.25
GANCO-AM greedy
2.90
0.01 %
0.3s
3,76
1.21% %
0.85
4.89
5.14%
2.15
Clustered
AM T0t
2,89
-0.28%
36
3.75
0.95%
8s
4,99
7.40%
216
GANCO-AM
2.89
-0.35%
3.73
0.37 %
8s
4.82
3.78%
AM T00
2.88
-0.50%
34s
3.75
0.29%
88s
4.92
5.95%
224s
GANCO-AM 100t
2.88
-0.54%
3,71
-0.13%
4.78
2.76%
218%
ILS
2.68
0.00%
1121s
3.65
0.00%
12893s
4.72
0.00%
63008s
ILS fast
2.71
1.14%
76s
3.69
1.64%
101s
4,83
2.16%
52.3%
AM greddy
2.69
0.43%
3.75
3.33%
5.23
2.36
Uniform
GANCO-AM greedy
2.69
0,38 %
0.3s
3,70
1.94%
0.9
4.99
5.74%
2.3s
AM
2.68
.0.0%%
38
3.70
2.00%
8%
5.13
8.65%
GANCO-AM 10:
2.68
-0.04%
36
3.67
1.13%
8s
4.94
4.51%
226
AM 100t
2.67
-0.26%
34s
3.68
1.23%
92s
5,06
7.18%
235g
GANCO-AM 100
2.67
-0,26 %
34s
3.65
0.64%
91s
4.90
3.65%
231s
ILS
2.49
0.00%
1242s
2.95
0.00%%
17265s
3.44
0.00%
830445
S
2.52
1.24%
70s
3.01
2.11%
122s
3,51
2.13%
7166s
AM greedy
2.51
0.73%
0.3s
3.23
9.69%
0.9s
4.62
34,47%
2.36
Diagonal
GANCO-AM greedy
2.50
0.37 %
0.3s
3,09
4.73%
0.95
3.97
15.53%
2.36
AM TÚL
2.49
0.023%
3%
3.12
6.06%
8s
4.46
29.68%
235
GANCO-AM 10:
2.48
-0.16%
36
3.04
3.09 %
8s
3.89
13.32%
22s
AM T00t
2,48
-0.28%
356
3.07
4.10%
92s
4.32
25.68%
234s
GANCO-AM 100t
2.48
-0.41% %
35s
3,01
2.04%
91s
3.82
11.29
229s
ILS
2,80
0.00%
949
3.59
0.00%
11168
4.48
0.00%
36622s
11.5 fast
2.82
0.83%
7
3.63
1.06%
99s
4.53
1.17%
505%
AM greedy
2811
0.31%
0.3s
3.68
2.70%
0.3s
4.94
10.21%
2.25
GANCO-AM greedl
2.81
0.31% %
3,66
1,97 %
4.74
5.76%
2.1s
Gaussion
AM T0E
2,80
-0.03%
36
3.65
1.60%
8s
4.84
8.06%
22s
GANCO.AN
2,80
3.63
1.19%
4.37%
21s
AM 100t
2.79
-0.21 %
34s
3.62
1.00%
888
4.78
6.66%
223s
GANCO-AM 100
2,80
.019%
34s
3.62
0.75%
86s
4.64
3.45%
21.5%
ILS
2.98
0.00%
952s
3.93
0.00%
11155s
4.96
0.00%
39783s
ILS fast
3.01
0.99%
72s
3.99
1.62%
106s
5.07
2.25%
471s
AM gready
2.99
0.15%
4.00
1.81%
3.40
8.83%
2.4x
TSPLIB-S
GANCO-AM greedy
2.99
0.08 %
0.3s
3.98
1.43%
0.9s
5.18
4.51%
2.2s
AM T0E
2.98
-0.20%
38
3.97
1.01%
8s
5,31
7.00%
236
GANCO-AM 10:
2.98
-0.24%
3s
3.96
0.75%
8s
5.12
3.30%
22s
AM T00t
2.97
-0.39%
356
3.95
0.56%
89s
3.24
5.68%
237s
GANCO-AM 100k
2.97
-0.40%
3,94
0.37
5.09
2.51%
half of the customer nodes, which follows the uniform distribution U(0, 4/n). And the penalties are designed to balance the importance of minimizing the tour distance and the cost of unvisited nodes, which follows the uniform distribution 3K/)). Particularly, K is fixed 2, and 4 for PCTSP with 20, 50 and 100 customers. The prizes and penalties are specifically designed to have meaningful instances. Therefore, for the generalization testing distributions, node prize and penalty distributions the same as the base training distribution. We only consider the generalization to different node coordinate distributions. The depot coordinates follow one of the three depot positioning (Central, Eccentric, Random) with equal probabilities. The customer coordinates follow the same generalization testing distributions as those for TSP.
keep the
In Table 8. we show the results of ILS, faster version of ILS, AM and GANCO-AM on PCTSP with different instance distributions. A faster version of ILS (ILS fast) uses the number of non- improvement iterations, the maximum iterations and the maximum reboot times as 200, 400 and 201 instead of the default 20000, 40000 and 4001 for the original ILS. The ILS fast is the non-learning baseline algorithm to train the generation model. Similarly, the GANCO framework improves the original AM by large margins on almost all the generalization testing settings. For the only exception (PCTSP20 with Gaussian), the performance of AM and GANCO-AM is almost identical. It is
18

---

Under review as a conference paper at ICLR 2022
Table 9; Results of AM and GANCO-AM for KP on instances with different distributions.
50
100
200
Dist.
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
DP
20.099
0.00%:
23s
40.404
0.00%
91s
57.730
0.00%
186s
AM greedy
20.081
0.092%
0.7s
40.383
0.052%
1.7s
$7.699
0.053%
GANCO-AM greody
20.080
0.096%
0.7s
40.381
0.056%
1.76
57.697
0.058%
3.98
TOE
20,088
0.053%
40.393
0.028
0.028%
GANCO-AM 10x
20.088
0.056%
66
40.792
0.029%
16s
57.712
0.031%
38s
AM 100L
20.092
0.036%
67s
40.397
0.018%
169s
57.721
0.015%
391s
GANCO O.AM 1001
20.091
0.039%
68s
40.397
0.018
173s
57.719
0.019%
404s
DP
18.915
0.00%
22s
38.0841
0.00%
975
53.754
0.00%%
182s
greedy
0.226%
0.8%
0.174%
0.390%
GANCO-AM greedy
18,880
0. A.186% %
0.8s
38,029
0.144%
2.
$3.654
0.184%
6.46
Clustered
AM
18.991
0.127%
88
58,048
0.094%
218
53.001
0,283
636
GANCO-AM 10t
18.895
0.110%
8s
38,052
0.084%
218
53.694
0.111%
648
AM TOOr
18,900
0.080%
81s
38. 062
0.037%
241s
53.637
0.217%
6776
GANCO-AM 100
18.901
0.074%
38.064
0.053%
239s
53.716
0.071%
7176
DP
18.783
0.00%
22s
37.757
0.00%
95s
50.819
0.00%
200s
AM greedy
18.741
0.223%
0.7s
37.695
0.163%
1.86
50.731
0.174%
4.18
GANCO-AM greedy
18.753
0.159%
0.7s
37.717
0.105 %
1.8s
50.748
0.140%
4.18
Uniform
AM T0E
18.757
0.137%
66
37.720
0.095%
18s
50.776
0.086%
41%
GANCO-AM 10x
18.764
0.097%
37.732
0.065
0.073%
AM TOOL
18,765
0.094%%
71s
37.733
0.061%%
1824
50.795
0.048%
43.3
GANCO-AM 100:
18.769
37.740
0.044%
182s
0.042%
DP
18.650
0.00%
25s
37,051
0.00%
90s
49.553
0.00%
194s
AM greedy
18.586
0.344%
0.7%
36.956
0.2029
1.8s
49.419
0,271
4.2%
GANCO-AM greody
18.620
0.158
0.7s
36.980
0.138 %
1.8s
49.436
0,236
Diagonal
AM TOE
18.612
0.202%
68
36.390
0.111
18s
49.477
0.134%
426
GANCO-AM 10c
18.634
0.084%
37.002
0.145%
42s
AM 100r
18.625
0.135%
71s
37,006
0.068%
182s
49.508
0.091 %
4456
GANCO-AM 100L
18.639
0.057%
71s
37.012
0.053%
182s
49.506
0,096%
444s
DP
T6.351
0.00%
22s
32.126
0.00%
976
32.127
0.00%
1936
AM greedy
16.319
0.196%
0.8s
32.088
0.120%
1.95
37.057
0.191
3.8s
GANCO-AM greedy
16.319
0.193
0.7s
0.116%
0.143%
3.8s
Gaussion
AM 10
16.334
0.103%
78
32.108
0.057% %
196
37.096
0.086%
38s
GANCO-AM 10x
16.333
0.107%
78
32. 127107
0.058%
19%
37,100
0.074%
38s
AM TOOI
16.341
75s
32,116
0.030%
2015
37.
0.1239%
4002%
GANCO-AM 100:
16.339
0.070%
75s
32.1
0.032%
203s
37.113
0.038%
403s
DP
18.917
37,850
51,699
18%
AM gready
18.887
0.15%
0.8s
37.799
0. 134%
2.0s
$1.579
0.233%
4.9%
GANCO AM greedy
18,889
0.148%
0.8%
37.810
0.105%
2.0s
51.621
0.151%
5.0s
TSPLJB.S
AM TOE
18,900
0.089%
75
37.821
0.075%
51.626
0,142%
49%
GANCO-AM 10t
18.899
0.092%
78
37.827
0.059 %
19s
$1.658
0.080%
49s
100L
18.906
0.058%
831
0.048%
2038
0.102%
GANCO-AR AM 1001
18.904
0.066%
75s
37.834
0.040%
211s
51.674
0.049%
498s
worth noting that for small size problem. AM and GANCO-AM can outperform the traditional non- learning methods that are highly optimized for the specific problems.
F AM EXPERIMENTS ON KP
Following Kwon et al. (2020), the item weights and values in KP are sampled from the unit uniform distribution U00 1) as the base training distribution. The weight capacity is fixed as 12.5, 25, 25 for the instances with 50, 100, 200 items. Considering the weights and values as the and y axis coordinates, we could leverage the same generalization testing distributions for TSP. The item weights are rounded decimal places for the Dynamic Programming (DP) algorithm attain the optimal solutions.
As shown in Table 9 for the greedy inferring, the GANCO framework effectively improves the performance on all the generalization testing distributions for different problem sizes. With more trajectories inferred, the performance of AM and GANCO-AM become fairly close on some distri- butions (such as Gaussian and TSPLIB-S) because KP is relatively simple problem and the order of node (item) sequences will not affect the solution. Therefore, multiple trajectories by sampling introduce more randomness to the solution quality and the performance slightly fluctuates.
19

---

Under review as a conference paper at ICLR 2022
G POMO EXPERIMENTS
We leverage AM the base model for most experiments given that it has been used in many other recent works including POMO, and exhibits good performance on a series of COPs. Here, we only consider TSP100 and CVRPI00 since the results of the improved AM in our experiments superior or close to those of POMO on the other sizes. Specifically, regarding TSP20 and TSP50, the gaps of AM are 0.14% and 0.73% compared to 0.12% and 0.64% for POMO. Regarding CVRP20 and CVRP50, the gaps of AM are 2.74% and 4.05% compared to 3.72% and 3,52% for POMO. Regarding KP50, KP100 and KP200, the gaps of AM are 0.092%, 0.052% and 0.053% compared to 0.130% 0.125% and 0.260% for POMO. However, POMO significantly outperforms AM on TSP100 and CVRPI00 (2.16% and 5.22% of AM for TSP100 and CVRP100 compared to 1.07% and 3.32%). Therefore, to further show that the proposed GANCO framework is model agnostic and general enough to other models, we conduct experiments on POMO to solve TSP100 and CVRP100.
The results of POMO and GANCO-POMO are shown in Table 10 and Table 3 for TSP100 and CVRP100, respectively. Both the results of single trajectory and 100 trajectories (the-multi-starting node strategy) are presented. Clearly, the improvement of GANCO- POMO over POMO is salient for both decoding methods.
Table 10: Results of POMO and GANCO-POMO for TSP100.
Concorde
single trajoctory
100 trajactories
Dist.
Obj.
Time
Method
Obj.
Gap
Time
Obj.
Gap
Time
Bose
7.76
142s
GANCO-POMO
POMO
7,85
7.84
1.20%
1.07%
2.2s
7,80
7.79
0.54%
0.45%
34s
PUMO
5.42
5.26%
5.26
2.29%
Clastered
5.15
210s
2.2s
34s
GANCO-POMO POMO
2.61%
1.15%
Uniform
5.30
183s
GANCO-POMO
POMO
5.56
5,39
4,97%
1.82%
2.2s
5,34
5.41
2.21%
0.75%
34s
POMO
21.78%
10.43%
Diagonal
3.24
1966
GANCO-POMO
3.30
2.12%
2.24
3,26
0.86%
34s
Goussian
5.70
167s
POMO
5,93
3,99%
2.2x
5,80
1.84%
34s
GANCO-POMO
5.82
2.07%
5.75
0.97%
POMO
5.93
2.97%
5.84
1.42%
TSPLIB-S
5.76
1.55%
2.2%
34s
GANCO-POMO
1.79%
0.74%
H MODIFICATIONS TO IMPROVE AM
We modify the base AM to improve its performance in two ways. Firstly, we remove the Batch Nor- malization layers as we find that they only help the model converge slightly faster at the beginning but harm the generalization performance on other distributions. Secondly, we train the model until full convergence instead of the fixed 100 epochs used in Kool et al. (2019). Therefore, the perfor- mance of the base model is much better than the original one (e.g.. 0. 0.14%, 0.73% 2.16% optimality gaps instead of the original 0.34%, 1.76%, 4.53% for TSP with 20, 50, 100 nodes).
In Table 11 layers. As the results are reported for 100 epochs in Kool et al. (2019). we start from there and present the results every 300 epochs until convergence. Clearly, after convergence, the performance without BN is better than with on various instance distributions including the training one. And the performance on most generalization distributions gets better with more training epochs. Even though the performance on some distributions could fluctuate or deteriorate, the best results on these distributions among different number of epochs are still far inferior to the ones attained after GANCO training.
we take TSP50 as an example and show the results of AM with and without the BN
To be more fair, we further compare GANCO-AM against variant of AM named AM-S, which is trained on the base distribution for the same number of steps (also the same number of instances) after the pretraining stage as GANCO-AM. Taking TSP50 as example, the average performance of AM (after the pretraining stage), AM-S and GANCO-AN on the five generalization distributions is 4.156, 4.168 and 3.989, respectively (the smaller the better). The generalization ability does not improve with more epochs for the original AM. And the improvement of GANCO over the other two models is clearly significant. The detailed results are shown in Table 11
20

---

Under review as a conference paper at ICLR 2022
Table 11: Results of AM with and without the Batch Normalization (BN) layers trained for different
number of epochs on TSP50.
100
400
700
1000
1300
AM-S (withour BN)
GANCO-AM (without BN)
Dist.
Models
epochs
spochs
epochs
epochs
opochs
Rase
AM with BN
5,806
5.753
5.740
5.735
5.731
5.735
AM without BN
5,825
5.755
5,740
5,733
5.729
5,729
Clustered
AM with BN
4.235
4.191
4.171
4.185
4.181
4.096
AM without BN
4,295
4.153
4.142
4.142
4.137
4.145
Uniform
AM with BN
4.214
4,080
4.219
4.159
4.226
3,970
BN
4,071
AM with BN
3.292
3,205
3,886
4,288
4,411
Diagomal
2.784
AM without BN
3,858
3.260
3.427
3.457
3.351
3,368
4.671
Gauvsion
4.542
AM without BN
4.743
4.639
4.659
4.691
4.671
4.684
TSPLIB-S
AM with BN
4.656
4.605
4.606
4.605
4.592
4.554
AM without BN
4,656
4.600
4.582
4.578
4.577
4.572
I MORE ANALYSIS ON GANCO FRAMEWORK
Table 12: Results of AM, AM-T4 and GANCO-AM for TSP100 and OP100. Distributions with are the AM-T4 training distributions.
TSPI00
OP100
AM-14
GANCO-AM
AM-14
GANCO-AM
Bose
7,93
1.97
7.94
32.40
32.22
32.30
Clastered
5.60
5.57
5.46
44.19
45.55
46.67
Uniform"
5.67
5.52
5,51
41.72
43.65
43.29
Diagonal*
5.22
3.50
3.47
44.61
52.76
51.37
Gaussian
35.16
TSPLIB
6.06
6.02
5.99
39.44
40.25
41.37
We conduct experiments of training the original AM on 4 distributions (base, uniform, diagonal, gaussian) after the pre-training stage, namely, AM-T4. The training dataset equally samples from the 4 distributions and AM-T4 is trained for the same number of steps (also the same number of instances) as the GANCO adversarial training stage. For TSPI00, the average performance of the original AM (after the pretraining stage), AM-T4 and GANCO-AM is 6.26, 5.82 and 5.75 on the four AM-T4 training distributions and 5.83, 5.79 and 5.73 on the other two generalization distributions (the smaller the better). For OP100, the average performance of the original AM, AM-T4 and GANCO-AM is 38.47, 41.22 and 41.07 on the four AM-T4 training distributions and 41, 42.90 and 44.02 the other two generalization distributions (larger collected prizes better). The detailed results are shown in Table 12
On the four distributions AM-T4 is trained on. GANCO-AM achieves comparable or better perfor- mance than AM-T4. The performance of GANCO-AM is better than AM-T4 on some distributions even though AM-T4 trains on these distributions. And AM-T4 underperforms the original AM on one AM-T4 training distribution (gaussian) for TSP100. This is because equally sampling from four distributions leads unbalanced reward (the rewards for instances with some distributions domi- nate the gradients). Instead of equally sampling from each of the four distributions, we also tried another simple composition rule (1/2 base distribution and 1/6 for each of the three generalization distributions) and the results are similar. In contrast, our GANCO framework uses the alternative training process to dynamically find the hard distributions and adjust the proportion of newly gener- ated distributions in the training dataset during the ad versarial training stage. Compared to AM-T4, GANCO-A achieves most of the benefits of training on in- de-distribution data.
More importantly, the two generalization distributions which both models do not train on, the average performance of GANCO-AM much better, which also demonstrates the improvement of generalization ability by training on adversarially generated distributions.
21

---

Under review as a conference paper at ICLR 2022
To demonstrate the adaptive nature of GANCO's adversarial instance generation, also conduct the experiments of training the agent for one problem (OP) on the distribution curriculum generated by GANCO for another agent for a different problem (PCTSP), namely, GANCO-AM-DIES The average performance of GANCO-AM--IIS on the five generalization distributions is 43.26, 43.55 and 43.90 with 5, 10 and 20 adversarial iterations (the larger the better for OP). In comparison, results of the original GANCO-AM for OP are 43.41, 43.73 and 44.00, respectively. Result of the original AM is 41.02. We can see that the performance of GANCO-AM-DIFF is also pretty good as these two problems are very similar with the distinction of flipping the constraint and objective value. However, the original GANCO-AM for OP performs better, suggesting that the generation model indeed tailors distributions bespoke to the specific problem.
22


Reviews:
[{"review_id": "jsEGfSjIyby", "reviewer": "Reviewer_sEuD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "**Strengths**\n\n- The paper is well written, the framework is presented clearly and (along with the supporting code promised to be released) with sufficient information to reproduce the key elements if the work.\n\n-  I find the task itself, improving generalisation in RL COP solvers, to be well motivated and prescient.  Indeed, most works learning solvers for combinatorial problems seek to test how they perform when the test-time distribution is different from that on which the solver was trained and I find the idea of dynamically controlling the training distribution to challenge the learnt heuristic to be an interesting approach.  To the best of my knowledge, the proposed framework is novel.\n\n- The experimental results are impressive, with the improved generalisation of agents trained within the GANCO framework clearly demonstrated with respect to those trained on only a single base distribution.  By considering multiple COP instances and using established methodologies, the empirical performance improvements are clear, however it there remains scope to further improve the analysis of GANCO itself as discussed below.\n\n**Weaknesses**\n\n- Whilst the broader distribution of training tasks provided by GANCO is clearly demonstrated to improve generalisation, the necessity of the adversarial entity (GANCO’s core contribution) is not demonstrated clearly enough to unequivocally endorse GANCO as an optimal (or very good) approach to generating additional instances.  To be precise, the RL baselines to which GANCO is compared are trained on strictly fewer instances sampled from a narrower distribution and for fewer steps overall, therefore it is unsurprising that GANCO performs better across different distributions at test time.  Whilst the authors do compare GANCO to a genetic based (GB) method for generating data, they also highlight that it is unsuitable for the task at hand: \"The resulting distribution [from GB] still approximately follows the base training distribution. It would be extremely hard for the genetic operators to attain instances following a significantly different distribution.”.  Given GANCO requires training a second adversarial agent (which comes with a significant overhead),  I believe justifying this additional training as necessary is important.  At the least, I would like to see comparisons to:\n\n \t1. The performance on an RL agent trained on multiple/all target distributions.  GANCO would, of course, not be expected to beat this, however it is unclear from the current results if GANCO is achieving most of the benefits of training on in-distribution data, or only providing fractional improvement compared to what could be achieved.\n\n\t2. The performance of an agent trained on the curriculum of instances generated by GANCO *from a different training run*.  It would be highly insightful to know whether it is the ability of GANCO to tailor instances bespoke to the current agent, or it is simply the ability to generate many significantly different distributions from the base distribution, that provides the bulk of the performance improvement.  If it was demonstrated that the adaptive nature of GANCO is key, this would, in my opinion, significantly strengthen the paper and further justify the design choices of the framework.\n\n- I do not believe Figure 2 is suitable as it is a set of ‘plots’ denoting how the authors hope GANCO will change the performance across a distribution (e.g. performance is strictly improved for all instances and all stages of the pipeline), and does not present any data or additional insight.  The intuition that providing additional data from distributions on which the agent performed poorly and help to learn more general policies is clear and suitably presented in the rest of the paper without the need for Figure 2, therefore I would suggest removing it.\n\n**Additional comments, question and errata**\n\n- The authors state that both the inputs to the generating network are sampled noise, and that the outputs are also per-node distributions from which node attributes are sampled.  What is the purpose of have two sources of stochasticity?  Initially I interpreted the input noise as sampling the specific problem instances distribution, and the output as sampling a value from this distribution.  However as the attributes for each node are sampled sequentially, presumably the input noise is resampled at each state too?  Of course it is not a major issue, but I would appreciate clarity for my own insight!\n\n- The authors claim that the challenge of generalising to out-of-distribution (OOD) test-time instances is “particularly severe for neural combinatorial optimization (NCO) models because the solution quality intricately depends on the instance distributions”.  Whilst I would agree that OOD generalisation is challenging and important, it is not clear to be that NCO models find it especially difficult compared to the multitude of other ML/RL applications.  Indeed, as solving COPs is often extremely (NP-)hard, an alternative stance would be that ML4CO models will never learn to analytically solve even in-distribution tasks of meaningful size, an so will instead naturally rely on sub-optimal heuristics that may in fact generalise quite well (e.g. a greedy algorithm is simple to learn, sub-optimal, but often shows good generalisation).  Could the authors clarify their meaning, or alternatively simply acknowledge that generalisation is difficult and important in general, with COPs being no exception?\n\n- Is there a particular reason the authors settled on alternately training the solver and generator, as a naive implementation might train both jointly (or indeed train exclusively on the generated instances)?\n\n- Typo in the caption of Fig 3c: (c) “CANCO-POMO on CVRP100”.\n", "summary_of_the_paper": "This work presents GANCO, a framework that extends the training of RL heuristics for combinatorial optimisation problems (COPs) to include an adversarial agent that aims to generate hard-to-solve problem instances.  The RL heuristic and adversarial instance generation are alternately trained, with the intuition that the adaptive problem distribution encourages the solving agent to learn policies with better generalisation performance to unseen instances compared to those trained on a single static distribution.  Experiments train the Attention Model of Kool et al (and a subsequent extension, POMO) within the GANCO framework and show that across multiple well-studied COPs (including the travelling salesman problem), GANCO augmented training does result in policies that generalise better to unseen distributions at test time.", "summary_of_the_review": "Whilst the GANCO framework is novel as a whole, it is the combination of existing ideas and methodologies (e.g, learning construction heuristics for CO problem and adversarial training).  The field of ML4CO is active the particular problem considered in the is work, generalising to OOD test-time data, is ubiquitous - therefore, in my opinion, the paper comfortably reaches the required standard in terms of novelty and potential interest.  Ultimately then, I believe it comes down to whether the demonstrated empirical performance is sufficiently strong, or if the core idea of adversarial instance generation is sufficiently well justified and investigated.  My feeling is that it is not clear cut, with the experimental results impressive, but to me only unequivocally demonstrating that training on a broader distribution of tasks results in a more general agent.  Overall, however, there is enough justification of the GANCO framework in the latter sections, for me to lean towards acceptance (ultimately, I find the ideas and results in the paper interesting, and therefore feel the same can be said for others working in the field).  With that said, I would be more confident and comfortable in my recommendation if the adaptive nature of the adversarial instance generation that is core to GANCO could be demonstrated as a key element in the frameworks empirical success (as discussed in detail in my main review).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "abu3aVwNIUx", "reviewer": "Reviewer_mumN", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "## Strengths\n1. The idea of generative adversarial training for combinatorial optimization is new.\n1. The experiment results are comprehensive and detailed, mainly on various settings of routing problems.\n1. Figure 1 presents a clear and straightforward overview of the proposed framework.\n\n## Weaknesses\n1. My first concern about this paper is the motivation and necessity for developing generative adversarial training methods for combinatorial optimization problems. Since we are handling a reinforcement learning problem without any supervision labels, it seems not very difficult to obtain a batch of problem instances that lie within the distribution of test instances (for example, loading the business data from last month and using them for training, and predicting on the next month). More aggressively, you may also train (or more properly, finetune) a neural network on the test instance if the time budget is acceptable. Besides, the results on the \"base\" distribution entry show that the performance of the model will probably degenerate after generative adversarial learning, but such property seems undesirable, especially we can easily obtain a batch of test instances in real-world applications.\n1. An assumption made in this paper is that the neural network has enough capacity to learn the input-to-optimal mapping of combinatorial problems from various distributions. If the network does not have enough capacity, the expressiveness of the neural network should be our major concern instead of the generalization ability. However, the results of neural networks, whether aided with adversarial learning or not, are all inferior to the traditional solvers. It makes me doubt the capacity of the current neural network models.\n2. Besides, is there any special design to prevent the neural network from \"forgetting\" the original distribution? The results on the \"base\" distribution entry show that the performance of the model will probably degenerate after generative adversarial learning, suggesting that the model seems incapable to learn the input-to-optimal mapping under the current pipeline and is likely to forget some information from the original distribution.\n1. Concerning the experiment part, it will be very interesting to see the result of traditional algorithms that are configured to run comparatively faster with learning-based methods. For example, the number of trials of LKH-3 is configurable to control the runtime of the heuristic and the current configuration (10000 trials as written in the appendix) seems too time-consuming. On page 7 the authors mentioned that \"Generally, their (the neural network's) run time is much shorter than the traditional algorithm as indicated in the table(s), which is a core strength of deep models.\" I doubt whether such a conclusion still holds if you replace your current solvers with a well-configured LKH-3 solver. It will make much more sense if you do not set a large number of trials for LKH-3 to force it to run super slow.\n1. The authors make an effort on including the knapsack problem. However, there is still room for further improvement if the authors can include more problems beyond routing problems because the title of this paper is claimed for general combinatorial optimization problems.\n1. The writing and formatting of this paper need to be improved to meet the quality of ICLR papers. See some examples in \"detailed comments\" below.\n\n## Other detailed comments:\n1. It seems unclear whether the objective function $O_\\Phi(x)$ is to be maximized or minimized. Maximizing or minimizing $O_\\Phi(x)$ will correspond to different formulations of $G(x,\\Phi, B)$.\n1. In Table 1, the inference times of AM and GANCO-AM are regarded as the same, which is reasonable because they share the same model architecture. And in Table 2 and 3, the inference times of AM/GANCO-AM and POMO/GANCO-POMO are different, which is also reasonable due to random noises in experiments. Although both of the writings may be reasonable, I think it will be better to maintain a consistent style of tables in one paper. \n2. In Table 2, the inference time of HGS (~0.5 hours for the smallest sized problem) seems unacceptable as an intermediate step when computing the reward signal in reinforcement learning. \n1. What is the time cost for the pertaining stage and the proposed adversarial training steps?\n", "summary_of_the_paper": "This paper presents a generative adversarial training pipeline for general combinatorial optimization problems, aiming to improve the generalization ability of learned neural network solvers on unseen data distributions. In experiments, the authors select the attention model as the neural network solver, and REINFORCE, POMO as the RL algorithms. The experiment results are comprehensive on various routing problems, and on the knapsack problem.", "summary_of_the_review": "The generative adversarial training for combinatorial optimization in this paper is novel, the experiment results are detailed and comprehensive. However, the motivation, writing, and the experiment part of this paper seem to have room for further improvement, and I am suggesting a rejection for this time and I am wishing to see an improved version in the future.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SB8HALcZva7", "reviewer": "Reviewer_tjCH", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The paper is reasonably well written, though section 3.1 would be easier to follow if the architecture of the generator model was described using a figure instead of just text. Moreover, since the authors evaluate their approach on optimizer models trained through reinforcement learning (according to section 2), I would have liked to see a discussion of other approaches that have been taken to improve the robustness of RL techniques in the related work section.\n\nThe evaluation section demonstrates empirically that data augmentation helps improve the performance of ML based combinatorial optimization techniques: it covers several enough combinatorial optimization problems (e.g TSP, CVRP, OP, PCTSP, KP) to give confidence to the reader that it is very likely to succeed on any combinatorial optimization problem. Furthermore, it evaluates the effectiveness of data augmentation in conjunction with 2 common optimizer models, AM and POMO, which indicates that data augmentation can be leveraged to improve the effectiveness of several prior work in this area.\n\nHowever, it is widely known that data augmentation helps the performance of neural networks, and the authors fail to demonstrate the effectiveness of their particular flavor of data augmentation. At the very least, they should have compared their approach against random data augmentation as well as against a simple policy that generates n examples, and keeps the k% of these n examples on which the optimizer model performs the worst. In other words, the paper needs to demonstrate that the generator model truly learns how to improve the quality of the dataset on which the optimizer model is trained. Put another way, the authors explain very well what they set out to accomplish in figure 2. They need to demonstrate in their evaluation that they accomplished this. \n", "summary_of_the_paper": "Over the last few years, several machine learning based approaches have been proposed to solve common combinatorial optimization problems, such as the traveling salesman problem. However, it's never been entirely clear how well the previous work generalized to out of distribution instances. This paper proposes to improve generalization through dataset augmentation.\nSpecifically, the paper proposes to train a model (aka the generator) that is used to drive the creation of training instances on which the neural network used to solve the combinatorial problem (aka the optimizer) does poorly. The authors then show that training the optimizer model on a set of examples taken from the original dataset as well as created under the guidance of the generator model results in better performance than training the optimizer model on the original dataset only. ", "summary_of_the_review": "This paper attempted to tackle an important problem which hasn't received the attention it deserved, namely ensuring that neural networks trained to solve combinatorial optimization problems generalize well. They proposed a theoretically sound approach to augment the original dataset with additional training examples created under the guidance of an auxiliary 'generator' model to cover the gaps in the original dataset. However, they failed to demonstrate that the effectiveness of this 'generator' based approach.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9yWy_SPf-5Z", "reviewer": "Reviewer_N945", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths:\n\n- paper is well written\n- good evaluation\n- intuitively understandable method with good results, both in terms of generalisation and speeding up training (which is expected due to other works establishing selecting tough training instances helping convergence)\n\nWeaknesses\n- the concept reminds me strongly of https://ai.googleblog.com/2021/03/paired-new-multi-agent-approach-for.html which should be cited \n- I wonder how much of the improvement is due to simply training on more examples? did you try generating random problem instances of multiple distributions and training AM for the same number of episodes? I'd still expect the adversarial method to be more universal, but if the distributions we might expect are somewhat known, domain randomisation can be computationally cheaper and simpler than this setup. Especially if a small subset of distributions can capture most of the expected variation across test distributions.\n\nOther comments:\n\n- instead of training in stages, did you attempt alternating the optimizer and the adversary on a per step basis?", "summary_of_the_paper": "The paper proposes a way to generate training examples for neural combinatorial optimisation  (NCO) methods (specifically evaluated on POMO and AM) that leverages an adversarial RL policy trained in stages to generate instances that maximise the performance advantage of a baseline CO method over the NCO method. The method is tested on a variety of CO problems and shows improved OOD generalization especially for larger problem instances.", "summary_of_the_review": "The paper presents an intuitive approach to generating training examples, makes it work and does a good evaluation. However, similar work has been done in the RL domain and other supervised training domains before (e.g. using GANs for data augmentations) so giving a marginal accept for now.  If the missing citation is added, my questions are answered and the edge the *adversarial* augmentation has over *random* augmentations (or simply perturbing the network slightly and training for longer) I'm willing to update my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: ## A Brief Summary
Recent works in deep learning have shown that it is possible to solve [[combinatorial optimization]] problems (COP) with neural networks.  However, generalization beyond the examples seen in the training set is still challenging, e.g., generalizing to TSP with more cities than the ones seen in the training set. This paper proposes the GANCO approach, where a separate generative neural network based on GAN generates new hard-to-solve training instances for the optimizer. The optimizer and the generative network are trained in an alternating fashion. The authors have run experiments with the attention model (AM) and POMO with their GAN-based data augmentation approach. The authors provide experimental results on several well-known COPs, such as the traveling salesman problem.

## Reviewers' Feedback

Below, I will summarize some reviewers' feedback and would like the authors to address the cons noted below.
### Reviewer sEuD

*Pros:*
- Paper is well-written.
- Task is important and well-motivated.
- Good experimental results.
*Cons:*
- The paper's core contribution on the necessity of adversarial entities is not well-motivated.
- Missing baselines:
- RL agent trained on all target distributions. To figure out how far GANCO is from the optimal policy.
- The performance of an agent trained on a curriculum.
- Figure 2 is unnecessary/redundant in the paper.



### Reviewer tjCH
*Cons:*
- The paper is reasonably written. However, it would be much easier to follow with a few changes. For example, section 3.1 explains the architecture and, in related works, a more comprehensive overview of the methods to improve the robustness of RL methods.
- It is widely known that data augmentation helps in deep learning. The paper's claims would be more convincing if it provided some crucial baselines, such as comparing different data augmentations methods and carefully ablating them.
  
### Reviewer N945
*Pros:*
- Well-written
- Good evaluation
- Simple model with good results
*Cons:*
- Missing citation to the PAIRED paper.
- How important are the adversarial entities generated? Is it possible to achieve similar results by just training on more samples?
- Missing baselines: Instead of training in stages, alternate optimizer and generator network per step basis.

### Reviewer mumN
*Pros:*
- The proposed approach is novel.
- Comprehensive and extensive experiments.
- Figure 1 provides a good summary of the approach.

*Cons:*
- Motivation is for the GANCO is not very convincing.
- Concerns about the capacity of the neural nets used in the paper.
- Concerns on forgetting the original distribution.
- Concerns about experimental evaluation protocol.
- Including experiments on routing problems to show the generality of the proposed approach.
- Request for improvements in the writing and the formatting of the paper.

## Key Takeaways and Thoughts
I think this paper attacks an interesting problem. As far as I am aware of the approach is novel. However, generative adversarial networks have been used in the machine learning literature for data augmentation and RL for augmenting the environment (see the PAIRED paper.) GAN type of approaches hasn't been used to improve the generalization of the deep learning approaches for COP. The results look promising. However, as pointed out by Reviewer mumN and tjCH, this paper would benefit more from further ablations, particularly the necessity of adversarial generation part to make the arguments more convincing. As it stands now, it is not clear where exactly the improvements are coming from. Reviewer mumN also raised some concerns about the poorly configured LHK3 baseline in the discussion period. Furthermore, I agree with the reviewer mumN and tjcH that this paper would benefit from restructuring to make it flow better. I do think that this paper needs another round of reviews. I would recommend the authors go over the feedback provided here and address them for future submission.## References
Decision: Reject