Data-efficient Supervised Learning is Powerful for Neural Combinatorial Optimization
Authors: Shunyu Yao
Xi Lin
Zhenkun Wang
Qingfu Zhang
Venue: Submitted to ICLR 2023 (2023)
Keywords: combinatorial optimization
data augmentation
neural combinatorial optimization
learning to optimize

Abstract: Neural combinatorial optimization (NCO) is a promising learning-based approach to solve difficult combinatorial optimization problems. However, how to efficiently train a powerful NCO solver remains challenging. The widely-used reinforcement learning method suffers from sparse rewards and low data efficiency, while the supervised learning approach requires a large number of high-quality solutions. In this work, we develop efficient methods to extract sufficient supervised information from limited labeled data, which can significantly overcome the main shortcoming of supervised learning. To be specific, we propose a set of efficient data augmentation methods and a novel bidirectional loss to better leverage the equivalent properties of problem instances, which finally lead to a promising supervised learning approach. The thorough experimental studies demonstrate our proposed method can achieve state-of-the-art performance on the traveling salesman problem (TSP) only with a small set of 50,000 labeled instances, while it also enjoys better generalization performance. We believe this somewhat surprising finding could lead to valuable rethinking on the value of efficient supervised learning for NCO.

Under review as a conference paper at ICLR 2023
SUPERVISED LEARNING IS POWER- FUL FOR NEURAL COMBINATORIAL OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Neural combinatorial optimization (NCO) is promising learning- baanin approach to solve difficult combinatorial optimization problems. However, how to effi- ciently train powerful NCO solver remains challenging. The widely-used re- inforcement learning method suffers from sparse rewards and low data efficiency, while the supervised learning approach requires a large number of high-quality solutions, In this work, we develop efficient methods to extract sufficient super- vised information from limited labeled data, which can significantly overcome the main shortcoming of supervised learning. For traveling salesman problem (TSP), a representative combinatorial optimization problem, we propose a set of efficient data augmentation methods and novel bidirectional loss to better leverage the equivalent properties problem instances, which finally lead to a promising su- pervised learning approach. The thorough experimental studies demonstrate our proposed method can achieve state-of-the-an performance on TSP only with a small set of 50, 000 labeled instances, while it also achieves promising general- ization performances on tasks with different sizes or different distributions. We believe this somewhat surprising finding could lead to valuable rethinking the value of efficient supervised learning for NCO.
INTRODUCTION
Many real-world applications involve chal- lenging combinatorial optimization problems, which could be NP-hard and cannot be exactly solved in reasonable time (Papadimitriou & Steiglitz 1998). The traditional approach needs to design handcrafted heuristic rules for each specific problem, and requires long search process to solve every problem instance even when they are similar each other (Korte al.) 2011). In recent years, many learning-bant baaed al- gorithms have been proposed efficiently find a good approximate solution for given prob- lem instance (Bengio al. 202T). p. In this work, we focus on the neural combinatorial optimiza- tion (NCO) approach (Bello et al. 2016) since it can directly generate an approximate solution in real-time without any expert knowledge or predefined heuristic rules.
TSP50
Original SL
SL-BL
2.00%
SL-DA
SL-DABL
Optimul Cup
POMO
POMO-DA
0.50%
0.25%
100
200
300
400
500
Epochs
Figure 1: The optimality gap of models trained with different training strategies on the validation set.
Although combinatorial optimization problem could be NP-hard, real-world application could typically only care about a small subset of instances (Bengio et al.) (021I. Therefore, it is possible to leverage the similar patterns shared by these instances learn efficient neural combinatorial solver (Vinyals et al. 2015). Supervised learning (SL) and reinforcement learning (RL) are the two main methods for training the NCO solver, which lear the pattern directly from high-quality solu- tions (Vinyals et al. 2015) or through extensive interaction with the environment (c.g., the problem instances) (Bello et al. 2016).

---

Under review as a conference paper at ICLR 2023
It challenging to efficiently train powerful NCO solver. The RL method suffers from the issues of
sparse rewards /Vecerik et al. 2017 Hare 2019) and low data efficiency (Laskin et al. 2020). which could require huge computational budget and lead to extremely long training time (e.g., more than week) (Joshi et 2020 Kwon et al. 2020). By directly learning from high-quality solutions at each step, the SL method has better sample efficiency and is promising alternative for training NCO solver (Joshi et al., 2019 2020). Nevertheless, SL suffers from the difficulty of collecting sufficient labeled data (i.e., optimal or near-optimal solutions of combinatorial optimization instances). In addition, there are also some concerns on the generalization performance of the NCO solver trained by the SL method (Joshi et al. 2020).
In this work, we investigate how to overcome the shortcomings of SL-based NCO training. By lever- aging the equivariance and symmetries of the problem instances and solutions, we develop novel approaches to extract sufficient information from limited high-quality solutions for data-efficient su- pervised learning, and we demonstrate that training POMO (Kwon et al. 2020) through our method is better than reinforcement learning. Our main contributions can be summarized as follows:
We design four simple yet efficient data augmentation approaches to significantly enlarge the training set from limited high-quality solutions, and develop novel bidirectional super- vised loss to leverage the equivalence of solutions to further improve the training efficiency for supervised learning. With these two powerful methods, propose novel Supervised Learning with Data Augmentation and Bidirectional Loss (SL-DABL) algorithm for TSP.
We conduct thorough experiments to study the efficiency of our proposed method. The results confirm that SL-DABL can achieve state-of-the-art performance on TSP with only 50, 000 training instances, and also has promising generalization performance to real- world instances with different sizes. These findings lead us to rethink some current beliefs NCO for TSP, such as (Joshi et al. 2020).
Our findings reported in this work could be somewhat surprising and opposite to some current beliefs about the NCO method. We show that 1) the huge supervised data requirement major drawback) indeed not necessary for SL and 2) RL is not always the best choice for training a NCO model. We hope they could be helpful for rethinking the role and value of efficient SL-based NCO training.
2 RELATED WORKS
In the past few years, many promising learning-based approaches have been proposed to tackle different combinatorial optimization problems. We briefly review the neural combinatorial opti- mization methods that are closely related this work, and refer readers to [Bengio al. (2021) and Cappart et al. 2021 for comprehensive surveys.
2.1
SUPERVISED LEARNING FOR NCO
Vinyals al. 2015)) proposed the Pointer Network with RNN encoder-decoder structure and atten- tion mechanism to solve TSP in an autoregressive manner. Milan et al.] (2017) found that it is costly generate enough high-quality solutions to serve as a training dataset for supervised learning, and proposed to update the initial dataset with superior solutions generated during the training process. Joshi al. (2019) trained graph neural network to predict the heatmap for each instance with non non-autoregressive decoding. The heatmap measures the probability that each edge will belong to the optimal solution, which can be converted to a valid solution with beam search, Monte Carlo tree search (Fu et al. 2021), guided local search (Hudson et al. 2021). ) and dynamic programming (Kool
et al. 2021)
Joshi et al. (2020) systematically studied the performance of different learning methods on both autoregressive and non-autoreeressive models. This work focuses on the construction-base au- toregressive model. According to the results in (Joshi et al.] 2020), even with 1, 280, 000 training instances, the SL approach will still be outperformed by the RL approach on the zero-shot greedy prediction for both testing and generalization performance. In this work, we propose novel data- efficient SL method to achieve state-of-the-as the- performance with 50, 000 training instances, which is only 4% of the training dataset in Joshi et al. 2020).
2

---

Under review as a conference paper at ICLR 2023
2.2
REINFORCHMENT LEARNING FOR NCO
Many RL-based methods have been proposed to train NCO solvers (Bello et al.
2016 Khalil et al.,
2017
Nazari al. 2018 Deudon al. 2018 Ma et al. 2019). Kool al. 2018) proposed the
Attention Model (AM) framework to solve different vehicle routing problems. Different follow-up
works have been developed to improve the AM performance with diverse solution generations (Xin) et al., 2021 Kim et al. (02T). Kwon et al. 2020) proposed the POMO method with multiple greedy rollouts leverage the multiple optima property, which is the current state-of-the-ard RI. algorithm for NCO. In this work, with the same model and inference strategy, our proposed SL-DABL method can outperform the RL counterpart in POMO for both testing and generalization performance.
Data augmentation is widely-used approach to increase the amount of training data for supervised learning (Shorten & Khoshgoftaar 2019; Feng et al. (02T). Kwon et al. (2020) have discussed how to use the data augmentation methods improve the inference performance for NCO but not for SL-based training. Recently, Geisler et al. (2022) have shown that augmenting adversarial examples into training could improve the NCO solver's ss robustness with small perturbations. In this work, we show that data augmentation is crucial for data-efficient SI-based NCO, but has little effect RL-based training. A concurrent work (Kim al., (022) used contrastive learning leverage the symmetric property of CO problems and solutions for better instance representation, which can improve the RL-based training. We believe these methods indeed orthogonal and could be complementary to each other.
Equivariant neural networks (Thomas al.. 2018 Satorras al. 2021). which can directly incor- porate the equivariance properties into the model structure, is a strong alternative to data augmenta- tion. this work, instead of building more powerful models, we focus on improving the supervised learning approach, and study whether it can outperform the reinforcement learning counterpart on the same model. Therefore, we left the study of equivariant neural networks for NCO future work.
DATA AUGMENTATION
In this section, propose four simple yet ef- ficient data augmentation (DA) approaches to significantly enlarge the training set from lim- ited high-quality solutions. By leveraging the translation invariance property of the problem instances, our proposed SL-DA method can extract sufficient information from the small dataset to train a powerful NCO solver as shown in Figure 2
TSP50
1A.0%
Optimal Glap-
Original SL
SL-DA
6.00%
3.1 PRELIMINARIES: TSP
200%
100
200 300
400
500
Epochs
TSP is the basic case of all the vehicle rout- ing problems, which aims to find the shortest trajectory т from fully connected graph S. In this work, we focus on the 2D Euclidean TSP, as it is common benchmark for most NCO algorithms. The fully connected graph be represented by set of n nodes in normalized 2D Cartesian co- ordinate, i.c., s; = (Ir, T with 2; [0, 1] and yı [0, 1] for i 2..
Figure 2: Supervised learning with/without effi- cient data augmentation on TSP50. Both methods only have 50, 000 training instances. The vanilla SL method struggles to train the NCO solver, while proposed SL-DA method has much bet- ter performance. The experimental setting for this analysis can be found in Section 3.6
(81, ($1,82.... .., 8,)
The outputted trajectory T = (2,,2,,.. .,.,,,,,,kk (n) is permutation of node indices, i.c. t E 21.2..... m} and t; # t, for any two different indices i.j E f1, n}. The cost of T calculated as
c(T[S)
Σ |tc.. St, 12 + ||sc. -s,,122. 112.
In this work, we represent the graph as [x, where x = [x), D2,...,,. [y, ......, . yn].
. Fnl and y =
3

---

Under review as a conference paper at ICLR 2023
04
180
023
039
0.7
028
822
035
021
825
675
E37
6.15
Detere
AftrMM
BoSee
Bcter
04
BoheeD
(a) Rotation
(b) Symmetry
(c) Shrink
(d) Noise
Figure 3: Examples of generating new instance via the (a) rotation operator, (b) symmetry operator,
(c) the shrink operator, and (d) the noise operator, respectively.
3.2 ROTATION
Each TSP instance is fully connected graph whose optimal solution is invariant with the rotation of the entire graph. Therefore, with single optimal solution given instance, we can generate multiple new instances by randomly rotating the original instance at different angles. The details of this rotation operator are provided in Algorithm
Algorithm Rotation
Algorithm 2 Symmetry
Input: the original graph S.
Input: the original graph S.
Output: the augmented graph S'.
Output: the augmented graph S'
1: [xm; Y + [x y.5:y y 0.5];
1: [Xm Ym < xx 0.5; 0.5):
2: p, 0 Cartesian2Polar(xx. ym):
2: p, 0 Cartessinn2ollar(x....
3: A0 ~ L((0,
3: A0 ~ (0)
4: 0' + 10:
0' < -0 A0):
5: Xmiin + Polar2Cartesian( 0');
5: Xmi <- Polar2Cartesian(p, 0');
6: S' [m + ym + 0.5);
S' Xm 0.5; 0.5];
As shown in lines 1-2 of Algorithm we first move the graph by changing its center from (0.5, 0.5)
to (0, T) and express the nodes in terms of the polar coordinates as
0 = arctan Ym
P
x2 + y
Xm
Then, randomly generate angle A (0,2x) then add it to the current @ get instance (i.e., lines 3-4 of Algorithm After that, we transform the new instance into the Cartesian coordinate system as
Xm p cos 0', Ym psin 0'.
Finally, the graph back to the location centered (0.5, 0.5)T and output the augmented graph S'.
Figure ((a] illustrates example of generating new instance via the rotation operator. It is clear that the new instance has the same optimal solution with the original one.
3.3 SYMMETRY
Similar to rotation, the optimal solution is also invariant to the symmetry operator. Since all nodes located in [0, 1 for uniformity, can set the axis of symmetry any line that passes through the midpoint (0.5, O.5)T.
Algorithm presents the symmetry operator in detail. Compared with the rotation operator, ad- ditionally flips the rotated graph along the horizontal axis of the polar coordinate system on line 4. The symmetry axis between the new graph and the original graph can be expressed
1 (1 - k)) where k = tan 2
A 2
y = kr
An example of generating the new instance via the symmetry operator is depicted Figure 3(b) We that both the original instance and the instance have the same optimal solution.

---

Under review as a conference paper at ICLR 2023
3.4 SHRINK
Algorithm: 3 Shrink
Algorithm 4 Noise
Input: original graph S, threshold parameter 7
Input: original graph S.
Output: augmented graph S'
Output: augmented graph S'.
1: Xmi Ym
0.5: 0.5]:
I: d NodeMiniiumDDitanckkk, y);
2: p, 0 <- Cartesian2Polarf Xm. mm):
2: rр ~ 44(0, 1);
3: B ~11(1 7; + 7):
3: ra 1((0,mm)
4: p' + Sp:
4: r grpi
5: Xmi Ym. Polar2Cartesianfp 0);
ra ry Polar2Cartesiantr, ro);
6: S' + X + y. + 0.5];
6: S' +- x rry):
The shrink operator linearly scales the original graph. Since the relative positions of all nodes are not changed, the optimal solution of the new instance the same as the original one. Similar to the rotation and symmetry operators, we use the midpoint (0.5, 0.5)T as the center for the shrink operator. The detailed procedure given in Algorithm
We first move the given instance to the new location such that its midpoint is (0. 0)T as in line 1, and map all nodes into the polar coordinate system as shown line 2 of Algorithm Then a coefficient is randomly sampled from U(1 7, 1 + 7) to control the zoom degree. The predefined threshold parameter y can prevent the graph from zooming to an extremely small or large scale. In this paper, set r to 0.3. The final step of Algorithm 3 restores the scaled graph to the original Cartesian coordinate.
In Figure 3(c) an example of generating new instance via the shrink operator is provided, where both the original and shrinking instance share the same optimal solution.
3.5 NOISE
Unlike the above three operators that perfectly preserve the relative positional relationship, the noise operator generates new graphs by randomly perturbing each node in the original graph. In other words, without any further restriction, the newly generated instances could have different optimal solutions to the original instance. This property undesirable for data augmentation.
However, the optimal solution could still keep the same if we only slightly change the node co- ordinates while qualitatively maintaining the relative position. To be specifie, we can add small enough noise to each node to perturb the graph such that the noise's upper bound is half the mini- mum distance between each pair of nodes 2' In this way, the nodes after perturbation will be small region around their original location and not overlap with each other. This tight restriction can also guarantee the newly generated instance will still have the same optimal solution as the original instance.
the noise operator in detail. As shown in line the minimal distance between each pair of nodes is calculated first. In lines 2-3, two coefficient vectors rр E (0, 1)" and (0, 2m)" are randomly sampled to determine the magnitude and direction of the noise, respectively. Finally, add the corresponding movements over the x and y axes as the noise for each node. This noise operator can adaptively set the noise upper bound and generate new graphs without changing the optimal solution. As the example illustrated in Figure 3(d) the optimality of the original label solution is guaranteed.
Eesorithm4deseeeiee
3.6 COMPARISON
These four DA operators can be applied independently or stacked together in a specific manner to generate new problem instances to support SL-based training. They also model-agnostic and can be used to train any SL-based NCO solver. In this subsection, we investigate their effectiveness for training the AM solver with the implementation in Kwon et al. (2020).
We compare the performance of the models trained by SL with different DA operators on the vali- dation set, which consists of 1,000 randomly generated instances. Both training and validation
5

---

Under review as a conference paper at ICLR 2023
TSP50
TSPS0
13.0%
13.0%%
Augmentation
Augmentation
Rotatin
All- Rotasio
-Symmery
All-Symmery
Strink
Al--Shrink
Optimal Gup
-Nose
All-Nosse
Optimal
6.0%
All
4.0%
3.%
460 990
1.0
206
Egoche
Epochs
Figure 4: The average optimal gap on the val- idation set generated by the Attention Model trained with supervised learning using each in- dividual DA operator.
Figure 5: The average optimal gap on the val- idation set generated by the Attention Model trained with supervised learning using com- bined DA operators.
50-node TSP instances (denoted as TSP50). The performance evaluated by the average optimal gap, and the optimal values are calculated by Concorde (Applegate al. 2006).
As shown in Figure 4 each of the proposed DA operators can improve the performance compared using the original training dataset directly. Specifically, the rotation and symmetry operators can remarkably alleviate the overfitting problem as well as reduce the optimal gap. In contrast, the effectiveness of using the shrink operator the noise operator separately not significant.
In addition to the performance assessment of each individual DA operator, we also investigate the efficiency of the combined DA operators. We stack all DA operators first and remove one of them for enumeration. For instance, the All-Rotation represents we employ all DA operators except the rotation operator. Since there is overlap in rotation and symmetry operators, we randomly employ one of them when using them both.
As shown in Figure 5 all kinds of combinations can significantly reduce optimal gap. The symmetry operator appears to be the most effective one, but the other operators also contribute to the performance improvement to varying degrees. In this paper, we adopt the combination of all four DA operations our DA strategy.
BIDIRECTIONAL Loss
In this section, by leveraging the equivalence of optimal solutions, propose novel bidirectional loss to further improve the data efficiency for SL-based training.
4.1 Loss FUNCTIONS
The construction- NCO solver se- quentially generates the solution in autoregressive manner, which selects
F == 3,2,,
4
0.8
one node at each step. The node se- lection can be viewed as a classification problem, and the goal of the SL-based method is to minimize the conditional cross-entropy loss from the optimal so- lution (Vinyals et al. 2015):
72 =25441 F
(325, =3.1,4452
7 (4,1,22 8 -(4,5,2,311)
= 4132) =(5,2,3,1,4
00
(a) solution for TSP
(b) Equivalent optimal solutions
L(S, 7) = Σ log Po 7 S7..
Figure Equivalent optimal solutions for TSP instance.
where 7' is the optimal solution for the corresponding instance S, S is the partial tour up to step t 1, 7, is the selected node at step t, and is the parameters of the training model.
However, a CO problem instance could have multiple optimal solutions (Kwon et al. 2020 Kotary al. 2021 As shown in Figure 6 for TSP instance with nodes and given optimal solution

---

Under review as a conference paper at ICLR 2023
have equivalent optimal solutions 7 with different starting node i. In addition, since the solution (tour) can move along the reverse direction, we can also have the other n optimal solution F'. Therefore, there are total 2n equivalent solutions to the single given optimal solution 7.
In this work, we propose a novel bidirectional loss function to leverage all the equivalent optimal solutions for data-efficient SL-based training:
(S, 7)
= 72 Σ A(C(S, C(S F()),
where -) denotes the aggregation function over the reverse directions from the same starting node, which can be one of (min, mean, max]. The min aggregation greedily optimizes the solution for the prefer direction, the mean aggregation considers solutions both directions, an the max aggregation optimizes the upper bound (e.g., the solutions with worse performance).
4.2 COMPARISON
In this subsection, compare the performance different aggrega- tions for the bidirectional loss with data augmentation. As shown in Figure 7 all aggregated bidirec- tional loss functions can outper- form the original supervised learn- ing function with the same amount of provided optimal solutions (e.g., 50, 000). Among the three differ- aggregation functions, the min aggregation achieves the best perfor- mance, and we use as the default setting in the rest of this work. An ab- lation study on the three aggregations with different settings can be found in Appendix.
TSP50
10.00%
Original SL
BL(Min)
BL(Mean)
BL(Max)
Optimal Gap
4.00%
1.00%
200
Epochs
Figure 7: The average optimal gaps the validation set with different loss functions.
4.3 SL-DABL
We combine the aforementioned data augmentation approaches and the bidi-
Algorithm 5 SL-DABL
rectional loss together to propose our Supervised Learning with Data Aug- mentation and Bidirectional Loss (SL- DABL) method as shown in Algo- rithm SL-DABL model-agnostic and can be used to train different construction-bant based NCO solvers. In this work, we adopt the same model struc- ture, hyperparameter settings, as well as the inference strategy with multi- ple starting nodes from POMO (Kwon
1: Input: the training dataset D, the number of train-
ing steps itermax the batch size B, and the shrink threshold parameter
Output: the trained model with parameters Φ²
3: Initialize the model with parameters Φ;
for iter l,..., itermax do
5:
S 7' ~ Sampleenstance(())
Vi E (1,...,B)) B):
6:
(/( 1);
7:
if a < 0.5 then
8:
S' Rotation(S)):
9:
else
eet al., 2020). In other words, the only difference is our proposed SL-DABL.
10:
S' Symmetry(S");
11:
end if
the RL-based training method with multiple rollouts developed in Kwon
12:
S Shrink 7))
13:
S Noise((')):
al. (2020). Following POMO, we also propose a variant (denoted as SL- DABL x8) that conducts additional x8 instance augmentation in the inference
VL(0) Σ VLn 7');
14:
15:
& +- ADAM VL()))
16: end for
phase.

---

Under review as a conference paper at ICLR 2023
5 EXPERIMENT
In this section, we first compare our SL.-DABL methoo with other widely-usede learning/non--eaninn -eeannnnn solvers on the uniform TSP instances. Then we conduct ablation studies to analyze each component of SL-DABL. Finally, SL-DABL compared against RL on the generalization ability to different problem sizes and real-world TSPLib instances.
5.1 OVERALL COMPARISON
TSP20
TSPS0
TSP100
Method
Type
Cost
Gap
Time
Cost
Gap
Time
Cost
Gap
TTme
Concorde
Solver
3.82473
0.000%
1.13m
5.69311
0.000%
6.66m
7,76541
0.000%
30.85m
Gumhi
Solver
3,8302
0.000%
2.35m
5.6905
0.000%
26.20m
7.7609
0.0009:
3.57h
LKHS
Heuristic
3,8303
0.000%
20.96m
5.6905
0.001
26.25m
7.7611
0.003%
49.96m
Wu (5000)
R
3.82551
0.020%
1.07h
5.70456
0,201
1.42h
7,88117
1.491%
1883h
Costa (2000)
RL, 1
3,82479
0.0021
28.45m
5.69957
0,114%
44.25m
7.82389
0.753%
1.06h
AM(Greedy)
RL
3.83565
0.285
0.35m
5,78875
1.680%
0.80m
8.10442
4.366%
1.80m
AM(Sampling)
RL
3.83694
0.319
0.42m
5.80361
1.941%
1.06m
8,15186
4.977%
2.05m
POMO
RL
3.82557
0.022%
0.01m
5,702388
0.163%
0.03m
7,82817
0.808%
0.17
POMO
RI. 3.82479
0.002%
0.08m
5.69507
0.035%
0.23m
7, 7.78218
0.216%
1.08m
POMO-DA
RL 3.82572
0.0266
0.01m
5. 3,70270
0,168%
0.03m
7 7,84934
1.081%
0.17m
POMO-DA X 8
RL
3,82480
0.002%
0.08m
5.69521
0.037%
0.25m
7.78944
0.309%
1.08m
GCN
0.10m
5.87
3.100%
8.380%
GCNT
BS
3.84
0. 100%
0.33m
5.71
0,260%
2m
7.92
2.110%
10m
GCN!
SL, BS
3.84
0.010%
12m
5.70
0,010%
18m
7.87
1.390%
40m
SL-DABL
SL
3.82496
0.006%
0.01m
5.69562
0.044%
0.03m
7,78793
0.290%
0. 0.17m
SL-DABL 8
SL
3,82473
0.000%
0.08m
5.69318
0.001%
0.23m
7.76925
0.049%
1.08m
Table 1: Experiment results on various TSP instances. In the Type column, RL: Reinforcement Learning, SL: Supervised Learning, I: Improvement, BS: Beam search with width 1280, and BS* Beam search with width 1280 and shortest tour heuristic.
As shown in Table 1 our two SL-DABL variants are compared with fourteen representative algo- rithms. At the top the table, Concorde (Applegate al. (006) and Gurobi (Gurobi Optimization, (022) are two exact solvers and LKH3 (Helsgaun) 2017) 7) powerful heuristic algorithm. The second group consists two learn-to-impe stam-to-improve algorithms, which are proposed by Wu (Wu et al. 2021) and Costa ed O Costa et al. 2020). respectively. The third group contains two RL-based NCO algorithms, AM (Kool et al., 2018) and POMO (Kwon et al.) 2020), each of which has two vari- ants. We also evaluate the performance of POMO trained thought reinforcement learning with data augmentation for clear ablation. The three GCN variants (Joshi et al. 2019) are Sla-b two-stage algorithms that generate solutions based the predicted heatmap. As for Gurobi, LKH3 and the three GCN variants, we directly use the results reported in Joshi et al. (2019) and Fu et al. (2021). We run the other algorithms by ourselves with the codes and pretrained models from their official implementations.
Following the common setting from other NCO work, we separately train three different models for TSP instances with 20-, 50- and 100-node (called TSP20/50/100, respectively). All training datasets are from (Hottung et al. 2020), where each one contains 50,000 TSP instances with optimal solutions solved by Concorde (Applegate et al.) 2006). We evaluate the performance and inference time on the test set with 10,000 randomly generated instances for each problem size.
From these results, can see that SL-DABL outperforms the other nine learning-based algorithms and achieve state-of-the-an results on all three kinds of TSP instances. Especially, SL-DABL x gains the same performance Concorde TSP20. Furthermore, our SL-DABL models inherit the real-time inference capability. which is significantly faster than exact and heuristic solvers as well as improvement-buut based algorithms. It is worth noting that SL-DABL outperforms POMO even though they have the same model structure and inference strategy. These results fully confirm that SL-DABL is data-efficient and powerful training method for NCO solvers.
5.2 ABLATION EXPERIMENT
To investigate the effectiveness of the DA approach and the bidirectional loss, we conduct ablation experiments each component of SL-DABL. We train the model with four different SL. strategies
8

---

Under review as a conference paper at ICLR 2023
(i.e., original SL, SL-BL, SL-DA, and SL-DABL) using the dataset of 50,000 labeled TSP instances of size 50. For comparison, we also train the model via RL using 51,000,000 random TSP50 in- stances. The five trained models compared the validation set of 1,000 random instances.
As shown in [i the original SL is overfitting after about 50 epochs due to the lack sufficient supervised data. In contrast, the SL-DA optimizes smoothly throughout the training stage without overfitting, and the only difference is that the training dataset is expanded by our proposed DA approach. The bidirectional loss also illustrates its effectiveness, especially when training data is insufficient. In the comparison of original SL and SL-BL, the bidirectional loss helps the latter moderately alleviate overfitting and extract more information from the limited tiny dataset in the early training stage. In the case of the training data containing tremendous labeled data, like SL- DA and SI,, the bidirectional loss can still further improve the data efficiency. SL.-DABI. more efficient than SL.-DA in getting information from the same amount of training data. SL-DABI. and SL-DA have similar performance at the end of training since they are very close the optimal solutions (e.g.. with 0.001% optimal gap). According to the results in Figure | the SL-DA and SL-DABL methods have better efficiency than RL throughout the whole training process.
In summary, the original SL approach is inferior to RL mainly due to the overfitting issue with lim- ited training data. Our proposed data augmentation approach can significantly help SL to extract sufficient supervised information from only 50, 000 training instances and thereby address the over- fitting issues with negligible cost. Meanwhile, the bidirectional loss can further improve the data efficiency, especially when the training set is relatively small.
5.3 GENERALIZATION
The generalization ability is an important concern for the learning-based NCO solver. In real-world applications. the problem instances could typically have different sizes and might come from dif- ferent distributions. It is crucial that the learning-basee solver should still be able to generate good approximate solutions for those unseen instances.
In this section, we compare the generaliza- tion ability SL-DABL and its RL coun- terpart with the POMO model and differ- ent inference strategies. We train two mod- els on TSP100 with SL-DABL and the RL. approach in POMO respectively, and then compare their performance on TSP instances with up to 300 nodes. As shown in Table generalization performance.
TSP150
TSP200
TSP250
TSP300
POMO
9,49834
11.00882
12.46317
13,89798
1099318
12.39314
13,84875
POMO SL-DABL
9,43073
10.91277
12.33501
13.73801
9.39082
10.84699
12,26284
13.67492
Table Generalization of models trained on TSP100
the model trained by SL-DABL always has the better
We also test our model on the widely-used TSPlib benchmark (Reincli, 1991) that contains real-world instances from dramatically differ-
SL-DABL 8
POMO
Size
Num
Num
Avg. Gap
Num
Avg. Gap
distributions. The statistical results on 30
100-150
17
1.462%
4
1.910%
2-D Euclidean instances with 100 to 300 nodes
151-200
5
4.571%
1
6.723%
201-250
2
3.663%
2
4.353%
are shown in Table SL-DABL outperforms its RL counterpart on 23 out of 30 instances and has better average optimal gap. The detailed results for each instance can be found in Appendix.
251-300
8.204%
10.697% 2
100-300
30
3.203%
7
4.286%
Table 3: Statistical results TSPlib
CONCLUSION
In this paper, we have proposed powerful SL-DABL method for learning traveling salesman prob- lem. It integrates data augmentation to efficiently extract sufficient supervised information from limited training data, and bidirectional loss to better exploit the equivalent properties of optimal so- lutions. The experiments have validated that SL-DABL can achieve sfate-of-ther the-art performance on TSP with only a small set of 50,000 labeled training instances, while also having better general- ization ability to its RL counterpart on real-world instances with various sizes. These findings could be helpful in rethinking the value of efficient SL methods for NCO training.

---

Under review as a conference paper at ICLR 2023
REFERENCES
David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde tsp solver, 2006.
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning, arXiv preprint arXiv:1611.099400 2016.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: a methodological tour d'horizon. European Journal of Operational Research, 290(2): 405-421, 2021.
Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. In Inter- national Joint Conferences on Artificial Intelligecce Organization, 2021.
Paulo R d O 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.
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the tsp by policy gradient. In International conference the integration of constraint programming, artificial intelligence, and operations research, pp- 170-181. Springer, 2018
Steven Y Feng, Varun Gangal, Jason Wei, Sarath Chandar, Soroush Vosoughi, Teruko Mita- mura, and Eduard Hovy. A survey of data augmentation approaches for nlp. arXiv preprint arXiv:2105.03075, 2021.
Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances. AAAI conference on artificial intelligence, 2021.
Simon Geisler, Johanna Sommer, Jan Schuchardt, Alcksandar Bojehevski, and Stephan Günnemann. Generalization of neural combinatorial solvers through the lens of adversarial robustness. In International Conference on Learning Representations (ICLR), 2022.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL https://www:
gurobi com
Joshua Hare. Dealing with sparse rewards in reinforcement learning. arXiv:1910.09281 2019.
arXiv preprint
Keld Helsgaun. An extension of the keemiighnn-hhlsauee tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, pp. 24-50, 2017.
André Hottung, Bhanu Bhandari. and Kevin Tiemeey. Learning latent search space for routing prob- lems using variational autoencoders. In International Conference on Learning Representations, 2020.
Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. arXiv preprint arXiv:2110.05291, 2021.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv: 000e6.002222 227, 2019.
Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning tsp
requires rethinking generalization. arXiv preprint arXiv:2006.0705. 07054, 2020.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti-
mization algorithms over graphs. Advances in Neural Information Processing Systems, 30, 2017.
Minsu Kim, Jinkyoo Park, et al. Learning collaborative policies to solve np-hard routing problems. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
10

---

Under review as a conference paper at ICLR 2023
Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-nco: Leveraging symmetricity for neural com- binatorial optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Wouter Kool, Herke Van Hoof, and Max Welling, Attention, learn solve routing problems! arXiv 2018.
preprint arXiv:1833.06.
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic pro-
gramming for vehicle routing problems. arXiv preprint 1rXiv:2102.17566 2021.
Bernhard H Korte, Jens Vygen, B Korte, and J Vygen. Combinatorial optinization, volume 1. Springer, 2011.
James Kotary, Ferdinando Fioretto, and Pascal Van Hentenryck. Learning hard optimization prob- lems: A data generation perspective. Advances in Neural Information Processing Systems, 34: 24981-24992, 2021.
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 18811188-211 18882199,,8,8 2020.
Misha Laskin, Kimin Lee, Adam Stooke, Lerrel Pinto, Pieter Abbeel, and Aravind Srinivas. Rein- forcement learning with augmented data. Advances neural information processing systems, 33: 19884-19895, 2020.
Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, and Iddo Drori. Combinatorial opti- mization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint arXiv:1911.04936. 2019.
Anton Milan, Hamid Rezatofighi, Ravi Garg, Anthony Dick, and lan Reid. Data-driven approxi- mations to np-hard problems. In Thirty-first AAAI conference artificial intelligence, 2017.
Mohammadreza Nazari, Afshin Oroojlooy, Martin Takáč, and Lawrence V Snyder. Reinforcement learning for solving the vehicle routing problem. Advances in Neural Information Processing Systems (NeurIPS), pp. 9861-9871, 2018.
Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and com- plexity, Courier Corporation, 1998.
Gerhard Reinelt. Tsplib - traveling salesman problem library. ORSA journal on computing, 3(4): 376-384, 1991.
Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E (n) equivariant graph neural net- works. In International Conference on Machine Learning (ICML), pp. 9323-9332, 2021.
Connor Shorten and Taghi M Khoshgoftaar. A survey on image data augmentation for deep learning. Journal of big data, 6(1):1-48, 2019.
Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation-and translation-qqiivariant neural networks for 3d point clouds. arXiv preprint 180.00/80..082/9 2018.
Mel Vecerik, Todd Hester, Jonathan Scholz, Fumin Wang, Olivier Pietquin, Bilal Piot, Nico- las Heess, Thomas Rothörl, Thomas Lampe, and Martin Riedmiller. Leveraging demonstra- tions for deep reinforcement learning on robotics problems with sparse rewards. arXiv preprint arXiv: 1007.0777.008//7 2017.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks. Advances in neural informa- tion processing systems, 28, 2015.
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuris- tics for solving routing problems.. IEEE transactions on neural networks and learning systems, 2021.
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, pp. 22042-12049 2021.

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
TSP20
TSP50
TSP100
Method
Type
Cost
Gup
Time
Cost
Gap
Time
Cost
Gap
Time
Concorde
Solver
3.82473
0.000%
1.13m
5.69311
0.000%
6.66m
7,76541
0.000%
30.85m
Gurobi
Solver
3.8302
0.000%
2.33m
5.6905
0.000%
26.20m
7,7609
0.000%
3.57h
LKHS
Houristic
3.8303
0.000%
20.96m
5,6905
0.001%
26.25m
7,7611
0.003%
49.96m
Wu (5000)
RI.1 3,82551
0.020%
1.07h
5. 5.70456
0.201
1.42h
7,88117
1.491%
1.83h
Costa (2000)
RL,
3,82479
0.002%
28.45m
5.69957
0.114%
44,23m
7,82389
0.753%
1.06h
AM(Greddy)
3,83565
0.285%
5,78875
1.680%
0.80m
8.10442
4.366%
1.80m
AM(Sampling)
RL
3,83994
0.319%
0.42m
5 8.3031
1.941%
1.06m
8.15186
4.977%
2.05m
POMO
RL
3.82557
0.022%
0.01m
5.70238
0.163%
0.03m
7.82817
0.808%
0.17m
POMO
RL 3.82479
0.002%
0.08m
5.69507
0.035%
0.23m
7,78218
0,216%
1.08m
POMO-DA
RL
3.82572
0.026%
0.01m
5.70270
0.168%
0.03m
7,84934
1.081%
0.17m
POMO-DA
3.82480
0.002%
0.08m
5.69521
0.037%
0.23m
7.78944
0.309%
1.08m
GCN!
SL
3.86
0.600%
0. 10m
5.87
3. 100%
0.92m
8.41
8,380%
6m
GCN!
S1., BS
3.84
0.100%
0.33m
5.71
0.260%
2m
7.92
2.1
10m
GCNT
ST, BS"
3.84
0.010%
5.70
0.010%
18m
7.87
1.390%
40m
SL. (MBL.Max)
SL
3,82502
0.008%
0.01m
5.69584
0.048%
0.03m
7,80461
0.505%
0.17m
SL-DABL(Max)
3.82473
0%
0.08m
5.69333
0.004%
0.23m
7.77544
0.129%
1.08m
SL. DMBL(Mea))
SL
3.82493
0.005%
0.01m
5.69525
0.038%
0.03m
7,7977
0.416%
0.17m
SL-DABI (M-ee)B x
3.82473
0%
0.08m
5.69323
0.0025
7.77352
0.104%
1.08m
SL-DABL(Min)
SL 3.82496
0.006%
0.01m
5,69562
0.044%
0.03m
7.78793
0,290%
0.17m
SL-DABL(Min)> X
SL
3.82473
0.000%
0.08m
5.69318
0.001%
0.23m
7.76925
0.049%
1.08m
Table 4: Experiment results on various TSP instances. In the Type column, RL: Reinforcement Learning, SL: Supervised Learning. I: Improvement, BS: Beam search with width 1280, and BS* Beam search with width 1280 and shortest tour heuristic.
TSP150
TSP200
TSP250
TSP300
TSP400
TSP500
RL DABL(Max)
9,49834
11 11.00882
12,46317
13,89798
16.6887
19.29866
9.47444
10.99099
12.44456
13.8601
16.5457
19,0202
(Meaa)))
9,46462
10.99342
12.48445
13,96524
16.84227
19.5274
SL-DABL((Mis)
9,43656
10:93318
12,39314
13884875
16.708
19.36179
RL X
9,43073
10.91277
12,33501
13.73801
16.48253
19,0658
-DABL/Ma))) x 8
9.4142
10,89508
12.31888
13.70788
16. 36.36537
18.8278
SL. DABL(Mean)
9.41023
10.89797
12.35213
13,80193
16.64035
19.30552
St SI-DABI(MMi) x 8
9.39082
10. 10.84699
12,26284
13.67492
16.4571
19.06886
Table 5: Generalization of models trained on TSP100
A.1 EXPERIMENTS SETTING
In this work, we plug our SL-DABL into POMO (Kwon et al.) 2020), and the details of the model can be found in the corresponding literature. We only describe the hyperparameter settings here, even though all of them are also identical to POMO: there are 100,000 data per epoch and the hatch size is 64. The models are optimized by the Adam optimizer in 510 epochs. In the first 500 epochs, the learning rate = le- 1e-4 4 with weight decay w = 1e-6, 6, while the last 10 epochs fine-tuning the model with 1 = le 5. The only difference between the training datasets of our SL-DABL and RL is that the former is augmented from tiny dataset consisting of 50,000 labeled data, while the latter randomly generated. Both of them use 51,00 1,000,000 data to optimize the models. All experiments are implemented on single Tesla V100 GPU.
A.2 BIDIRECTIONAL LOSS ABLATION
In this part, we extend the overall comparison with the models trained through the other two ag- gregated bidirectional loss functions Max and Min. As shown in Tabel 4 all variants of SL-DABL outperform all other learning-basse baselines.
A.3 ABLATION OF TRAINING DATASET SIZES
12

---

Under review as a conference paper at ICLR 2023
Size
SL-DABL(Min) SL-DABL/Mean) SL-DABL(Max)
RL
kmA 100
0.475%
0.296%
0.700%
1.001%
kruB100
0.528%
0.628%
0.944%
0.917%
kmC100
kroD100
0,329%
1.437%
0,498%
2.268%
kroE100
0.924%
1.156%
0.952%
0.430%
rd100
0.607%
0.670%
0.607%
0.721%
eil101
11.44%%
11.288%
447%
12.0839
lin
0.814%
1.44%
0.0%%
1.523%
pc107
0.553
1.205%
0.851%
0.973%
pe124
0.349%
0.317%
bier127
1.828%
1.501
5 5.391
3 3,049%
ch130
1.277%
1.538%
1,889
1.358%
pc136
1,296%
1,296%
0.933%
1.217%
pr144
0.530%
1.2866%
1 5505%
0.516%
ch150
1.762%
2.436%
2. 2.252%
2 2.068%
kroA150
10000%
1.327%
1,244%%
I. L.90%
kroB150
1,50%%
pr152
1.160%
2.600%
1 1.900%
1.952%
u15y
0.3025
0.326%
0.368%
1.236%
rat195
8.6339
10.891%
11 58088
17.1
d198
13. 13.219%
26.857%
23 169%
195%
kroA200
2.023%
3,780%
2.390%
1.82%
kroB200
2.072%
3.526%
3.849%
2.952%
ts225
1.725%
2.883%
4,469%
1sp225
5.720%
5.6699
7.380%
6.691%
pe226
3.544
7.709%
4.109%
1,899%
gi1262
9.504
10.050%
9.548%
9,420%
Pr264
6,112%
9,979%
8.175%
8. 133%%
7,988%
11.245%
10.741%
13.455%
p+299
9.213%
12.199%
13.328%
11.780%
Avg. Gap for 100-150
1.462%
1.708%
1.957%
1.907%
Avg. Gap for 151-200
4.571%
7.997%
7.209%
6.723%
Avg. Gap for 201-250
3.663%
5.794%
4.790%
4, 4.353%
Avg. Gap for 251-300
8.204
10.868%
10.448%
10.697%
Avg. Gap for all instances
3,203%
4.595%
4,423%
4.286%
Table 6: Results TSPlib
TSP50
In this subsection, study the ef- fect of different numbers labeled instances (e.g.. 10K and 100K) for
4.00%
Original SL
SL-DABL-10k
2.00%
SL-DABL-5OK
our proposed SL-DABL method. As
SL-DABL-100K
shown in Figure g the proposed ef- ficient SL-DABL method with only
Optimal Gap
1.00%
POMO
10k instances will suffer from over- fitting, yet which is significantly al- leviated compared the original SL. method. In addition, its performance still better than the reinforcement learning counterpart. In practice, the overfitting issue might be properly handled by early stopping. On the other hand, the improvement on in- creasing the labeled instances from 50K to 100K is not significant.
0.50%
0.10%
100
200
4001
500
Epochs
Figure 8: Ablation of training dataset sizes
A.4 GENERALIZATION
We firstly discuss the generalization of the models trained on TSP100 up TSP500. As shown in Tabel the SL-DABL with max aggregate function superior to RL in all test sets. In addition, the min one has better performance on TSP100-TSP300.
The details of the performance on TSBlib are depicted in Tabel 6
A.5 CAPACITATED VEHICLE ROUTING PROBLEMS
13

---

Under review as a conference paper at ICLR 2023
VRP20
In this subsection, investigate the effect of our proposed SL-DABL method the capacitated vehicle routing problens(CVRP). Most ex- perimental setting is the same with the TSP experiment, and we have 10k: labeled training instances where the solutions are achieved by the pow- erful LKH solver (Helsgaun) 2017). We also slightly modified the data augmentation and loss function ac- commodate CVRP. For data augmen- tation, to guarantee the optimality of original solutions, the noise approach removed since the additional depot hampers the design of the noise up- per bound. For the loss function, the sub-tours of given (near-)optimal lutions are reordered to find the most similar one based on the current model. The purpose of this operation to alleviate the influence of the equivalent solutions. Therefore, different from the 2n equivalent solutions in TSP instances, there are m!2m equivalent solutions for each CVRP instance, where is the number of sub-tour.
6.45
Original SL
Cost
6.35
SI--ABL
POMO
6.30
6.5
100
200
300
400
500
Epochs
Figure 9: The cost of models trained with different training
strategies on the validation set.
CVRP20
As shown in Figure 9 for CVRP20, our SL-DABL significantly mitigates the overfitting compared the original SL, and the per- formance is stably superior to POMO. And the numerical result can be checked out Table
POMO
6,20833
POMO x
6.16887
SL-DABL 8
6.15666
Table 7:
Experiment results
various CVRP instances
A.6 GCN
TSP20
In this subsection, investigate the performance our proposed data augmentation approaches on the GCN model (Joshi et al.) (019). Since the GCN model directly pre-
GCN
0.080%
GCN-DA
Optimal Gap
0.020%
dicts the solution heatmap an ad- jacency matrix, the bidirectional loss functions is not capable in this set-
ting. We follow the same experi- ment settings as reported in the main paper.As shown in Figure I0 for TSP20, our data augmentation still modestly improve the performance for the GCN model, even if both of them employ the beam search ap- proach with 1280 width.
0.005
0.003%
600
1000
1200
Epochs
Figure 10: The optimality gap of GCN trained with different training strategies on the validation set.
14


Reviews:
[{"review_id": "xm6BsrsnRw", "reviewer": "Reviewer_3o4f", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The paper proposes a new supervised-learning method for combinatorial optimization problems. One of the main contributions of the paper is the introduction of four types of data augmentation in training (i.e., Rotation, Symmetry, Shrink, and Noise). Another contribution is a new bidirectional loss, in which given the optimal solution, the training process will only minimize the autoregressive likelihood for the starting point and direction of minimal loss. Experiments show that due to more informative gradients from the annotation, the supervised neural solver can outperform reinforcement learning methods on TSP-20/50/100 problems.", "summary_of_the_review": "The paper provides a strong empirical study of data-efficient supervised learning for NCO, and could help the NCO community rethink the role and value (e.g., generalization & convergence speed) of SL and RL. However, the data augmentation method and bidirectional loss proposed in the paper are not very novel in my opinion.\n\nTherefore, I would recommend a score of 5 for the paper.\n", "strength_and_weaknesses": "Strength\n\n1. The paper proposes to train the supervised learning (SL) method with the POMO framework, i.e., autoregressive decoding, and show that with data augmentation and a novel loss objective, SL can actually achieve better performance than reinforcement learning (RL), which overthrows the conclusion from [1].\n\n2. The empirical results also show that the SL method trained on TSP-100 can achieve better performance on TSP-150/200/250/300 than RL (i.e., POMO) method, which again overthrows the conclusion from [1].\n\n3. Overall, I believe the results from this paper could help the NCO community rethink the role and value of SL and RL.\n\n\nWeaknesses\n\n1. My main concern is the empirical effectiveness of data augmentation. As shown in the paper, in four types of data augmentation in training (i.e., Rotation, Symmetry, Shrink, Noise), rotation and symmetry are the most effective ones. However, in the graph neural network community, equivariant neural networks [2,3] can directly model an equivariant function without any data augmentation and significantly outperforms data augmentation methods. I am wondering if the authors have considered these equivariant neural networks.\n\n2. The idea of minimizing the minimal loss from a set of candidates is not new in the literature of combinatorial optimization. For example, [4] applied it to the minimum independent set problem.\n\n\nTypos:\n\nPage 3: \"Kwon et al. (2020) has discussed how to use the data augmentation methods to improve the inference\nperformance for NCO but not for RL-based training.\" ==> \"have\", \"but not for *SL*-based training.\"\n\n\n[1] Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning tsp requires rethinking generalization. arXiv preprint arXiv:2006.07054, 2020.\n\n[2] N. Thomas, T. Smidt, Steven M. Kearnes, Lusann Yang, L. Li, Kai Kohlhoff, and P. Riley. Tensor field networks: Rotation- and translation-equivariant neural networks for 3d point clouds. ArXiv, 2018.\n\n[3] Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E(n) equivariant graph neural networks, 2021b.\n\n[4] Li, Zhuwen, Qifeng Chen, and Vladlen Koltun. \"Combinatorial optimization with graph convolutional networks and guided tree search.\" Advances in neural information processing systems 31 (2018).", "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": "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": "wWhcga-BY1h", "reviewer": "Reviewer_VFpH", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper proposes a supervised learning algorithm called Supervised Learning with Data Augmentation and Bidirectional Loss (SL-DABL) for traveling salesman problems (TSP). There are two components in the approach. The data augmentation method leverages several equivalence properties of traveling TSP, e.g., the optimal solutions stay the same for problems transformed with rotation, horizontal flip, scaling, etc. The bidirectional loss leverages the fact that the same route can be represented in different ways, e.g., via starting from different nodes. They evaluate their approach in the setting where there are 50K training samples with optimal solutions, and compare their approach to several reinforcement learning and supervised learning baselines as well as the non-learning-based solvers. They demonstrate that their approach achieves better optimality gap compared to learning-based approaches, while the inference time is also much shorter than classic non-learning solvers for combinatorial optimization problems.", "summary_of_the_review": "This work presents good empirical results for TSP compared to prior learning-based approaches. However, the proposed approach is specific to TSP, and is not generally applicable to other combinatorial optimization problems. Meanwhile, the evaluation setting is a bit restricted, and some aspects of the approach are not well-studied. Therefore, I recommend a rejection.\n\n\n----------\nI thank the authors for the response and new experiments. I understand that the time for revision and adding experiments is short, but I still feel that the current experiments are insufficient and the scope of this work is limited. So I keep my score.", "strength_and_weaknesses": "Strengths:\n\n1. The proposed approach is simple yet effective for solving TSP with neural networks, and it is model-agnostic.\n\n2. Their approach achieves better generalization to larger TSP instances compared to the POMO baseline.\n\nWeaknesses:\n\nOverall, I think the proposed approach is specific to TSP. Both data augmentation and bidirectional loss design leverage the properties of TSP itself, and are not applicable to most other combinatorial optimization problems. To show that the approach is effective for more problems, the authors should also present results on Capacitated Vehicle Routing problems (CVRP), where there have been several works on designing learning algorithms for CVRP (e.g., [1][2][3][4]).\n\nMeanwhile, I wonder whether the proposed SL-DABL algorithm is effective for different training data sizes. In general, the advantage of RL approaches is that they do not require optimal solutions for training. While 50K samples in the current setting is smaller than some prior works, it is not a small number either. Therefore, it is helpful to study how SL-DABL compares to other baselines when the training size is even smaller, and whether the approach can achieve better performance with more training data.\n\nAlso, the authors should study the effect of SL-DABL with different model architectures, especially those with some equivariance properties already incorporated in the architectural design. For example, the authors can evaluate on GCN and see whether their training algorithm can improve the performance.\n\n[1] Kool et al., Attention, Learn to Solve Routing Problems! ICLR 2019.\n[2] Nazari et al.,  Reinforcement Learning for Solving the Vehicle Routing Problem, NeurIPS 2018.\n[3] Chen and Tian, Learning to Perform Local Rewriting for Combinatorial Optimization, NeurIPS 2019. \n[4] Kwon et al., POMO: Policy Optimization with Multiple Optima for Reinforcement Learning, NeurIPS 2020.", "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": "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": "v6qT0uKEyT", "reviewer": "Reviewer_1fJi", "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": "", "summary_of_the_paper": "This paper considers supervised training of neural networks for solving combinatorial optimization problems. They study the effect of data augmentations on generalization. The key finding is that data augmentations are key to successful training (and non0overfitting) of supervised training, whilst reinforcement learning based approaches to learning neural solvers do not benefit from data augmentations. ", "summary_of_the_review": "Whilst the authors are pursuing an important and open question of how to train more effective neural solvers for combinatorial problems, the current paper lacks novelty or conceptual contribution. I would suggest to the authors that they generalize their results to other problems, or seek more depth in their TSP studies. ", "strength_and_weaknesses": "The underly idea of this work is the following: combinatorial optimization problems often have symmetries, where certain modifications to the problem do not change its solution. Since these modifications do not change the solution they make suitable data augmentations for use during training [or indeed better still the invariances are built into the model architecture]. There may also be modifications of the problem that do change the solution, but change it in a predictable, easily computed way, some of which are considered in this work. \n\n**Strengths**\n\n- Paper is clearly written and easy to quickly ingest the main points and contributions.\n- Observation that RL doesn't benefit from augmentations while supervised does is interesting.\n\n**Weaknesses** \n- The paper is not suitably contextualized within the contributions of prior work. The appearance is given that augmentations have not been considered before for neural combinatorial optimization. But this is far from true - for instance this paper https://arxiv.org/pdf/2110.10942.pdf also considered data augmentations for TSP. Although I am not certain myself, I would not be surprised if another reviewer is aware of prior work on augmentations and RL for NCO - RL for NCL is a really well studied area so the idea that people do not already know that augmentations are not all that useful sounds unlikely to me [but I will wait on this last point to see if anyone actually knows a suitable reference for this].\n- Contributions are stated in a more general form than they actually manifest. Specifically, the authors consistently conflate \"neural combinatorial optimization\" (NCO) with the TSP problem. For instance the phrase \"With these two powerful methods, we propose a novel Supervised Learning with Data Augmentation and Bidirectional Loss (SL-DABL) algorithm for NCO training\". This algorithm isn't a general NCO method, it is specific to TSP.\n- Evaluation is limited to TSP. \n", "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": "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": "lJelD4xAy-L", "reviewer": "Reviewer_Ke1k", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The paper develops a methodology based on supervised learning (as opposed to reinforcement learning) for the purpose of neural combinatorial optimization (NCO), and in particular for the traveling salesman problem (TSP). In this direction, the authors first propose a set of four data augmentation methods (rotation, symmetry, shrink and noise), which augments the original set of data without affecting the label of the optimal solution. This allows to extract sufficient information from a small set of high-quality labeled solutions.  Subsequently, the authors introduce a new bidirectional supervised loss, which  leverages the equivalence of solutions for the TSP, e.g., a path remains an optimal solution is we reverse the directionality of all edges, or if we cyclically shift the path by any amount. The paper then builds upon these two ideas and introduces the SL-DABL algorithm for NCO training.\n\nThe authors then conduct an extensive experimental study, where they train POMO with their supervised learning framework (instead of reinforcement learning), and show that they can achieve state-of-the-art results with only 50,000 high-quality training instances. Furthermore, they provide encouraging results of better generalization performance to test instances of different sizes that the training instances.", "summary_of_the_review": "The paper is well-written and proposes a sound framework for improving the TSP problem with supervised learning. The empirical results look good, even though I am not personally clear that the generalization power for the new framework is strong. The main reason why I am on the fence is because I feel that both the scope and the novelty are not significant, which is a concern for a top-tier venue like ICLR.", "strength_and_weaknesses": "Strength\n- The paper is well written and simple to follow. The various ideas are clearly stated and written down in sufficient detail.\n- The motivation is interesting. RL may not necessarily be the best choice for training, as the authors argue. They provide an interesting alternative and are able to outperform POMO training with RL. Their results on TSP20, TSP50 and TSP100 are state-of-the-art compared to the surveyed approaches and thus supportive of the proposed supervised framework.\n- Despite being simple, the proposed ideas are based on sound theoretical fundamentals (e.g., invariance of optimal solutions under certain transformations).\n- The experimental compares to various solvers (traditional and NCO). Furthermore, the ablation study sheds light on the individual components of the proposed framework.\n\nWeaknesses\n- The paper makes a bold statement already in the title, i.e., that supervised learning is powerful for NCO. However, both the theory and the experiments are specifically tailored for the TSP problem. I am concerned that this big claim is not really supported in the paper. The scope of the paper is limited to TSP, and any evidence in favor of NCO will necessarily come from TSP only. This is not just about being precise. My main source of concern is that the proposed data augmentations and bidirectional loss are mainly meaningful for the TSP, but may not be applicable for other challenging combinatorial problems such as capacitated vehicle routing problem, or the 0-1 knapsack problem. If the authors wanted to make such a general statement, then they should have studied more problems (with possibly different sets of data augmentations and invariances/symmetries), and show that supervised learning is powerful for these problems, too.\n- Related to the problem above, the scope is limited. I think the paper would have benefitted from including more problems, or alternatively, by arguing how the proposed ideas are more widely applicable to problems other than TSP. In the current exposition, it seems to me that the story is almost exclusively about TSP.\n- The generalization results are somehow encouraging - indeed, compared to POMO with RL, the proposed framework achieves better results. However, I am not convinced that the proposed symmetries can inherently improve generalization to instances of varying lengths. I think they should enhance learning efficiency for instances of a fixed length, and this is aligned with the results on TSP20, TSP50, and TSP100. But I do not really see how their design can inherently lead to improved generalization. Also, note that POMO with RL suffers from poor generalization power - so, even if the proposed framework improves upon POMO with RL, this alone is not necessarily a sign of good generalization power.\n- The novelty is not strong. The proposed framework is mostly based on simple properties of the TSP problem. This is not necessarily a problem by itself, but it could be an issue when coupled with the limited scope of the paper.", "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": "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": "Yl1RdiJxJi", "reviewer": "Reviewer_5UpA", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "Neural Combinatorial Optimization (NCO) with supervised learning suffers from data inefficiency when applied to the Traveling Salesman Problem (TSP). This paper proposes a series of data augmentations using properties such as rotation and symmetry invariance of TSP solutions in 2-D, along with a bidirectional loss function. With only 50,000 training examples, the proposed algorithm achieves SOTA on 2-D TSP.\n", "summary_of_the_review": "Overall, the paper is interesting and presents intuitive methods. It is easy to read and the results are well-supported. My key question remains on whether it is generalizable beyond TSPs only.", "strength_and_weaknesses": "Strengths\n- The overall idea is intuitive and simple. The augmentations are easy to implement and the bidirectional loss is neat.\n\nWeaknesses\n- In Algorithm 5, what is the motivation for the augmentation procedure of rotation or symmetry + shrink + noise? An intuitive augmentation procedure would be to employ random chance of rotation + random chance of symmetry + random chance of shrink + random chance of noise.\n- It seems like the strategies are geared towards TSP problems, but what about other combinatorial optimization problems? Do the frameworks scale to all CO problems that can be formulated on graphs?", "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:

Decision: Reject