Year: 2021

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.

heading: 1 INTRODUCTION
text: Combinatorial Optimization Problems (COPs) are a 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 important 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 its variants can provide elegant theoretical guarantees but the worst-case computational complexity is exponential, hence impractical 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 a 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 facilitate 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 in a routing problem may uniformly scatter in an area), deep models can be trained to learn heuristics in an end-to-end way (Dai et al., 2017; Kool et al., 2019; Chen & Tian, 2019). It 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 a different distribution, 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 distributions is always an important issue for most learning based methods. Especially, for neural combinatorial 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. (2021)) and remains a challenge.
To tackle this issue, we propose the Generative Adversarial Neural Combinatorial Optimization (GANCO) framework which is model agnostic and generally applicable to various neural combinatorial 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 a generation model to produce training instances following the distributions on which the optimization 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 improve 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.
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)) on 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)).

heading: 2 RELATED WORKS
text: Most deep learning models are trained to 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. (2021); 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 a 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 operators (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 are 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 is 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 (Pinto et al., 2017; Khirodkar et al., 2018; Dennis et al., 2020). However, existing works in this direction are not directly applicable to our task due to its 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 a hard instance generator, which is evaluated by performance gaps of the optimization model with respect to a traditional non-learning baseline 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 existing 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 reinforcement learning and improve the generalization performance for neural combinatorial optimization models. In our experiments, we also verify the necessity of our data generation method.

heading: 3 MODEL
text: For most learning based methods, the patterns are learned from the training data and usually applicable to 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 inference 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 a 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 1. Rather than training the optimization model solely on instances sampled from the predefined training distribution, we also deploy another deep learning model to generate instances on which the optimization model performs poorly. The generation model is trained by reinforcement learning to maximize the performance gap between the optimization model and a non-learning baseline algorithm on the generated instances. And the optimization model is trained with the generated samples to improve the performance on similar instances. In other 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.

heading: 3.1 GENERATION MODEL
text: As suggested in existing works (Kool et al., 2019; Kwon et al., 2020), many important COPs can be viewed as a 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 as by determining the presence of each edge for problems depending on the graph connectivity (e.g., the Boolean Satisfiability Problem).
The generation model Ω 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 ∈ Rn×2 as 2-dimensional variables for each node j = 1, .., n following the unit uniform distribution independently, i.e., h ∼ U(0, 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-forward layers with Batch Normalization (Ioffe & Szegedy, 2015) and skip connection (He et al., 2016). The noise input is node-wise linearly projected to H-dimension and encoded by k self-attention blocks. And another node-wise linear layer with a sigmoid activation projects the hidden vectors to the output distribution parameters Ω(h) ∈ Rn×d where d is the number of attributes for each node. Then we draw the sample x̃ from the Gaussian distribution N (µ, σ2)
with mean µ = Ω(h) and fixed standard deviation σ. The network outputs are kept in the same range [0, 1] to use the same variance for different attributes. The sample x̃ is scaled to the corresponding valid ranges (and discretized for discrete attributes) to attain the node attributes x = A(x̃).
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 objective values alone are not meaningful enough to evaluate the model performance. Although the optimality gap appears to be a good alternative metric in this case, it often requires expensive computation 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 distributions, compared to the learning based methods. Therefore, the performance gaps of the optimization model with respect to a traditional non-learning baseline algorithm could be regarded as a 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 state of RL environment is the noise input h ∈ Rn×2. The action is to sample the attribute values for a node. An episode is to sample the attribute values x = A(x̃) with x̃ ∼ N (Ω(h), σ2) for all the nodes to form an instance. However, as the sampled attributes for one node will not affect the other nodes, the episode can 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,
L(Ω) = −Eh∼U(0,1),x̃∼N (Ω(h),σ2)G(x,Φ, B), (1)
where G(x,Φ, B) = (OΦ(x) − OB(x))/OB(x) is the performance (objective) gap1; OΦ(x) and OB(x) are the objective values of the solutions found by the optimization model Φ and the baseline algorithm B for the generated instance x, respectively. Different from the generator in GAN (Goodfellow et al., 2014) 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 generation model is trained by the REINFORCE algorithm (Sutton et al., 2000) with reward baseline as the mean of the gaps in a batch. The gradient to train the generation model is expressed as follow,
∇ΩL(Ω) ≈ − 1
N N∑ i=1 G(xi,Φ, B)− 1 N N∑ j=1 G(xj ,Φ, B) ∇ΩlogN (x̃i; Ω(hi), σ2) , (2) where i and j are the instance indices; N is the batch size; x̃i ∈ Rn×d ∼ N (Ω(hi), σ2); and N (x̃i; Ω(hi), σ2) is the probability of x̃i sampled from the Gaussian distribution N (Ω(hi), σ2).

heading: 3.2 GANCO FRAMEWORK
text: The formal flow of the GANCO framework is summarized in Algorithm 1. The GANCO framework is 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 distribution. Then the optimization model is trained with instances sampled from the augmented distribution to improve the performance on new instances while preserving the performance on old ones.
1Here we follow the convention to formulate the COPs as minimizing the objective functions. The maximization problem can be viewed as minimizing the negative objective.
Generation Training At the beginning of each adversarial iteration, the parameters of the generation model are 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 to learn diverse instance distributions. Specifically, the generation model is trained using the gradients in Eq. (2).
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 performance on both the base training distributions and the adversarial generated distributions, we maintain 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 a 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 RL, we sample new instances from these distributions for each epoch following the composition rule above.
Algorithm 1 Generative Adversarial Neural Combinatorial Optimization Input: Optimization model Φ, generation model Ω, the non-learning baseline algorithm B, the
base training distribution Do, the number of adversarial iterations Na, the number of training iterations NΩ for Ω and the number of training epochs NΦ for Φ in an adversarial iteration, the learning rate η and batch size N for Ω. Output: Generative adversarial trained optimization model Φ 1: 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 Do 5: for ka ← 1 to Na do ▷ Adversarial Training Stage 6: Randomly initialize the parameters for Ω 7: for kΩ ← 1 to NΩ do ▷ kath Generation Training 8: Sample the noise inputs h ∈ RN×n×2, and infer the distribution parameters µ = Ω(h) 9: for i← 1 to N do 10: Sample the instances xi with x̃i ∼ N (µi, σ2), and use Φ and B to solve xi 11: end for 12: Ω← Ω− η∇ΩL(Ω) 13: end for 14: Augment D with the distribution generated by Ω 15: for kΦ ← 1 to NΦ do ▷ kath Optimization Training 16: Sample dataset X from D following dataset composition rule, and train Φ on dataset X 17: end for 18: end for

heading: 4 EXPERIMENTS AND ANALYSIS
text: We adopt the Attention Model (AM, Kool et al. (2019)) as the optimization model to verify the effectiveness of our proposed GANCO framework. AM is a widely used strong deep learning model for a series of routing problems and other COPs such as the Knapsack Problem. It is also used as the base model in many other recent works, e.g., Kwon et al. (2020); Xin et al. (2021); Hottung et al. (2021). As a heuristic model that learns to 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 in Lu et al. (2020). Typically, AM consists of an encoder and a 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.
We use AM to solve TSP, CVRP, OP, PCTSP and KP in our 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 on problems) with batch size 100 and attribute standard deviation σ 0.05, and the optimization model is trained for 20 epochs with 256000 instances in each. The hyper-parameters for model architecture and optimizer are the same as 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 (2020)), 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 termination for HGS as 100 instead of the default 20000 to save training time. Also, we exploit a 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, we apply the GANCO framework to another prevailing optimization model, i.e., POMO (Kwon 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.

heading: 4.1 TRAVELING SALESMAN PROBLEM
text: 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 et al. (2017); (2) Uniform: the nodes are uniformly sampled in a rectangle with random aspect ratios; (3) Diagonal: the nodes are distributed near the diagonal of rectangle; (4) Gaussian: 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 are presented in Appendix A.
The results of Concorde, AM (with greedy decoding) and GANCO-AM are gathered in Table 1, where we report the average objective values and gaps, and the total time for solving the 10000 test-
ing instances sampled from each distribution, respectively. For the traditional algorithm Concorde, we run 20 instances in parallel on a 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 run time is much shorter than the traditional algorithm as indicated in the table(s), which is a core strength of deep models. Clearly, GANCO-AM improves the performance on various generalization testing sets (i.e., the last five distributions in Table 1) 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 to 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 is fairly acceptable.
A more complete comparison with other methods is presented in Appendix A, 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 on fixed-size instances (n = 20, 50, 100 for routing problems), we also demonstrate that GANCO-AM significantly improves the results of AM on 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.

heading: 4.2 CAPACITATED VEHICLE ROUTING PROBLEM
text: 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 or a corner in the unit square, following CVRPLIB (Uchoa et al., 2017). For the customer demands, we adopt six distributions based on CVRPLIB. Particularly, they are sampled from {1, ..., 9} (Original) or {1, 2} (Small) or {8, 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 a few large ones (SL), respectively. More details for the testing sets are presented in Appendix C.
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 is small. In 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).

heading: 4.3 ORIENTEERING PROBLEM, PRIZE COLLECTING TSP AND 0-1 KNAPSACK PROBLEM
text: We also apply the GANCO framework on 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 one reported in its original work, where the customer prizes increase with the distance to the depot. The base distribution for KP follows the setting in Kwon et al. (2020). More details for problem settings, generalization testing distributions and results are presented in Appendix D, E and F for 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% to 7.67%, 7.33% and 0.17%, respectively).

heading: 4.4 POLICY OPTIMIZATION WITH MULTIPLE OPTIMA
text: To demonstrate that the GANCO framework is model agnostic, we further apply it to 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 as reported in Kwon et al. (2020). In Table 3, we record the results of POMO and GANCO-POMO by inferring a single trajectory and 100 trajectories (with the multi-starting-node strategy) for solving CVRP100. Clearly, the improvement of GANCO-POMO 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).

heading: 4.5 ANALYSIS ON THE GANCO FRAMEWORK
text: In Figure 2, we plot the objective gaps of GANCO models on various testing sets along adversarial iterations for TSP or CVRP, where iteration 0 refers to 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 on some testing sets especially for the early iterations, the
performance on those generalization testing sets becomes more desirable and stable quickly as the iteration increases.
Similarly, in Figure 3, 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 iteration increases, indicating that the lower bound of performance is pushed up with our GANCO. Furthermore, even before we train the model on a generated distribution (the diagonal polyline), the performance on it also usually tends to become better, which verified the effectiveness 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 in Appendix A.
Though deep learning models still perform relatively inferior to strong traditional algorithms on well-studied COPs, GANCO framework effectively improves the gen-
eralization ability. With certain settings for the less studied problems, deep models performs favorably against the traditional ones (e.g., inferring 10 trajectories on PCTSP50, GANCO-AM improves the average gaps on testing sets from 2.32% to 1.31% with average run time 8s for 10000 instances, compared to 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 (GANCOAM for CVRP100) costs less than 3 days compared to the 14 days for pretraining of AM. Furthermore, 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, we conduct more experiments in Appendix I. We demonstrate that GANCO achieves most of the benefits of training on in-distribution data and achieves better generalization performances compared to the model trained with multiple distributions. Furthermore, the generation model tailors distributions bespoke to the specific problem.

heading: 5 CONCLUSION AND FUTURE WORK
text: In this paper, we propose the GANCO framework to 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 our 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 to tackle much larger instances.

heading: A AM EXPERIMENTS ON TSP
text: For the Traveling Salesman Problem (TSP), the base training instances are 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.
1. Clustered: Following Uchoa et al. (2017), 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 × 1000 grid, the cluster centers are uniformly and independently sampled. A node is located at location p with probability proportional to∑S
s=i exp(−w(p, s)/0.04), where s is the cluster index and w(p, s) is the distance between location p and cluster center s. All nodes in an instance are located at distinct points in the grid.
2. Uniform: For each instance, the nodes are distributed uniformly in a 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, a rectangle is generated in the same way as in Uniform and a noise size t is sampled from the uniform distribution U(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 U(−t, t) are imposed for the horizontal and vertical axes, respectively, to attain the node coordinates.
4. Gaussian: For each instance, a correlation coefficient ρ is sampled from the uniform distribution U(0, 1). The nodes follow the bivariate Gaussian distribution with the mean (0.5, 0.5), the standard deviation 1 for both axes, and the correlation coefficient ρ. However, 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 (Reinelt, 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-Clustered node distribution in Uchoa et al. (2017), where half of the 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.
In Table 4, 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 a highly optimized exact solver for TSP, which finds the optimal solutions in a fairly short time. LKH (Helsgaun, 2000) uses the same hyper-parameters (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.e., inferring 10 trajectories (10t) and 100 trajectories (100t). In the greedy version, the node to visit at each step is selected as the one with the highest probability. More solution trajectories could be achieved by sampling the node to visit at 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 or 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 et al. (2020) to 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
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
mutated with probability 1/ √ n to be replaced with a random number sampled from the unit uniform distribution (n is the number of nodes). And same as GANCO, the objective gaps of the optimization 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 is trained on the new dataset. For a 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 4, 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 approximately 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 a Combinatorial Optimization Problem. Therefore, to tackle such a relatively hard task, we exploit a deep model trained with reinforcement learning, which is fairly effective as we have demonstrated in the experiments.

heading: B AM EXPERIMENTS ON TSPLIB
text: 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.95% 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 300-1000 nodes. Nevertheless, the GANCO-AM still improves the generalization performance over AM.

heading: C AM EXPERIMENTS ON CVRP
text: We detail the instance distributions for CVRP. The base training distribution is acquired from Kool et al. (2019), where the coordinates of customers and depot follow the unit uniform distribution, and the demands are uniformly sampled from the integers {1, ..., 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 distributions 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 5 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, ..., 9}. 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 {1, ..., 9}.
In Table 6, we show the results of HGS, a faster version of HGS, LKH3, the original AM and GANCO-AM on the various instance distributions. Hybrid Genetic Search (HGS, Vidal et al. (2012); Vidal (2020)) combines genetic algorithm with local search, which is considered as the state-of-the-art algorithm for CVRP. The faster version of HGS (HGS fast) uses the number of nonimprovement 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 use the same hyper-parameters (SPECIAL parameters, 10000 trials, 1 run) as those used in Kool et al. (2019). For distributions with small demands (Small) where the number of nodes in a route is 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), LKH3 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.

heading: D AM EXPERIMENTS ON OP
text: 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 to the depot. The base training distribu-
tion is 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 ρi of node i is determined by ρi = 1100⌊1 + 99× w0i maxnj=1w0j
⌋, where w0i is the distance between depot and node i. Therefore, 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 (Central, 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.

heading: E AM EXPERIMENTS ON PCTSP
text: 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
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 U(0, 3K/n). Particularly, K is fixed as 2, 3 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, we keep the 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.
In Table 8, we show the results of ILS, a 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 nonimprovement 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
worth noting that for small size problem, AM and GANCO-AM can outperform the traditional nonlearning methods that are highly optimized for the specific problems.

heading: F AM EXPERIMENTS ON KP
text: Following Kwon et al. (2020), the item weights and values in KP are sampled from the unit uniform distribution U(0, 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 x and y axis coordinates, we could leverage the same generalization testing distributions for TSP. The item weights are rounded to 2 decimal places for the Dynamic Programming (DP) algorithm to 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 distributions (such as Gaussian and TSPLIB-S) because KP is a 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.

heading: G POMO EXPERIMENTS
text: We leverage AM as 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 CVRP100 since the results of the improved AM in our experiments are 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 CVRP100 (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-startingnode strategy) are presented. Clearly, the improvement of GANCO-POMO over POMO is salient for both decoding methods.

heading: H MODIFICATIONS TO IMPROVE AM
text: We modify the base AM to improve its performance in two ways. Firstly, we remove the Batch Normalization 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 performance of the base model is much better than the original one (e.g., 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, we take TSP50 as an example and show the results of AM with and without the BN 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.
To be more fair, we further compare GANCO-AM against a 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 an example, the average performance of AM (after the pretraining stage), AM-S and GANCO-AM 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.

heading: I MORE ANALYSIS ON GANCO FRAMEWORK
text: 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 TSP100, 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.82, 42.90 and 44.02 on the other two generalization distributions (larger collected prizes are better). The detailed results are shown in Table 12.
On the four distributions AM-T4 is trained on, GANCO-AM achieves comparable or better performance 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 to unbalanced reward (the rewards for instances with some distributions dominate 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 generated distributions in the training dataset during the adversarial training stage. Compared to AM-T4, GANCO-AM achieves most of the benefits of training on in-distribution data.
More importantly, on the two generalization distributions which both models do not train on, the average performance of GANCO-AM is much better, which also demonstrates the improvement of generalization ability by training on adversarially generated distributions.
To demonstrate the adaptive nature of GANCO’s adversarial instance generation, we 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-DIFF. The average performance of GANCO-AM-DIFF 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.

Review summaries:
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.

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. Specifically, 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. 

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.