Generalization in Deep RL for TSP Problems via Equivariance and Local Search
Authors: Wenbin Ouyang
Yisen Wang
Paul Weng
Shaochen Han
Venue: ICLR 2022 Submitted (2022)
Keywords: Deep Reinforcemenet Learning
Travelling salesman problem
Curriculum Learning
Equivariance
Local Search

Abstract: Deep reinforcement learning (RL) has proved to be a competitive heuristic for solving small-sized instances of traveling salesman problems (TSP), but its performance on larger-sized instances is insufficient. Since training on large instances is impractical, we design a novel deep RL approach with a focus on generalizability. Our proposition consisting of a simple deep learning architecture that learns with novel RL training techniques exploits two main ideas. First, we exploit equivariance to facilitate training. Second, we interleave efficient local search heuristics with the usual RL training to smooth the value landscape. In order to validate the whole approach, we empirically evaluate our proposition on random and realistic TSP problems against relevant state-of-the-art deep RL methods. Moreover, we present an ablation study to understand the contribution of each of its components.

Under review as a conference paper at ICLR 2022
GENERALIZATION IN DEEP RL FOR TSP PROBLEMS VIA EQUIVARIANCE AND LOCAL SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
Deep reinforcement learning (RL) has proved to be competitive heuristic for solving small-sized instances of traveling salesman problems (TSP), but its perfor- mance on larger-size sized instances is insufficient. Since training on large instances is impractical, we design novel deep RL approach with a focus on generalizability. Our proposition consisting of simple deep learning architecture that learns with novel RL training techniques, exploits two main ideas. First, we exploit equivari- ance to facilitate training. Second, we interleave efficient local search heuristics with the usual RL training to smooth the value landscape. In order to validate the whole approach, we empirically evaluate our proposition random and realistic TSP problems against relevant state-of-the-ae deep RL methods. Moreover, we present ablation study to understand the contribution of each of its components.
INTRODUCTION
The traveling salesman problem (TSP) has numerous applications from supply chain management (Snyder & Shen 2019) to electronic design automation (Gerez, 1999) bioinformatics (Jones & Pevzner 2004). As an NP-hard problem, solving large-sized problem instances is generally in- tractable. Deep reinforcement learning (RL)- bdaee heuristic solvers have been demonstrated (Bello et al. 2016 Dai et al.) [017]] Kool et al., 2019 Ma et al.) (219) as being able to provide compet- itive solutions while being fast, which is crucial many domains such logistics for real-time operations. However, this ability has only been demonstrated on small-sized problems where RL- based solvers are usually trained and tested on small instances. When evaluated instead on larger instances, such solvers perform poorly. Since the computational cost of training large instances is prohibitive, increasing the size of the training instances not a practical option for obtaining efficient solvers for larger instances. To overcome this limitation, this paper investigates techniques to increase the generalization capability of deep RL solvers, which would allow to train on small instances and then solve larger ones.
Generalization in deep RL (François-Lave, et al. 2018) can be improved by adjusting the follow- ing three components: input/representation space, objective function, and learning algorithm. We propose to achieve this by exploiting equivariance, local search, and stochastic curriculum learning, which we explain next. Although our approach is demonstrated on TSP problems, we believe can be naturally extended to other combinatorial optimization problems, but also to more classic RL domains. We leave this for future work.
Problems with spatial information, such TSP problems, enjoy many spatial symmetries which can be exploited for RL training and generalization. RL solver is invariant with respect some symmetry, if its outputs remain unchanged for symmetric inputs. For instance, translating all the city positions leave optimal solutions intact. More generally, an RI. solver is equivariant, if outputs also transformed with corresponding symmetry for symmetric inputs. For instance, if cities are permuted, a corresponding permutation required on the outputs of the RL solver. Invariance and equivariance of the solver with respect some symmetries allows smaller input space to be considered during training and more abstract representation insensitive to those symmetries to be learned while the trained solver still covers the whole input space.
Previous work has considered using local search as a simple additional step to improve the feasible solution output by RL-based solver. In contrast to most previous work, we further employ local

---

Under review as a conference paper at ICLR 2022
search as tool smooth the objective function optimized during RL training. To that aim, interleave RL training with local search using the improved solution provided by the latter to train the RL solver via modified policy gradient. Moreover, we propose novel simple baseline called the policy rollout baseline to reduce the variance of its estimation.
Curriculum learning (Soviany al. 202 can accelerate training, but also improve generalization (Weinshall et al.] 2018). By stochastically adjusting the difficulty of the training instances, as de- scribed by instance sizes, the RL-based solver can learn more easily and faster. Since the solver sees various sizes of instances, this may prevent it to overfit to one particular instance size.
The architecture of our model includes graph neural network (GNN), a multi-layer perceptron (MLP), and an attention mechanism. Due to all the used techniques, we name our model as eMAGIC (e for equivariance, M for MLP, A for Attention, G for Graph neural network, for Interleaved local search, and C for Stochastic Curriculum learning). We demonstrate that it can be trained on small random instances (up to 50 cities) and perform competitively on larger random or realistic instances (up to 1000 cities). The only learning methods that can perform better than ours require learning on the instance to be solved (see Section 2 for a discussion).
2 RELATED WORK
Research on exploiting deep learning
Vinyall al. 2015 Li ct al.
2018
Joshi al.
2019a 9ap Prates
lt al.
2019
Xing & Tu 2020 or RL Bello et al. 2016 Dai et al.
2017 70771 Kool et al.
2019 [eudonn
ct al.
2018
Ma et al. 2019 Da Costa al. 2020 Zheng et al. 2021 Kwon et al. 2021] Wu al.
202 to design heuristics for solving TSP problems has become very active. The current achieve-
approaches, but also reveal their usual limitation solving larger-size instances, which has prompted much research generalization (Joshi et al., 2019b; Fu et al. 2021 Wu et al. (222b)) Some experimental work (Joshi et al. 2019b) suggests that deep RL may provide more generalizable solvers than supervised learning, which is further motivation for our own work. Another advantage of deep RL is that it does not require opti- mal solvers to train. We discuss next the related work that exploits equivariance our method. To the best of our knowledge, no other work uses stochastic curriculum learning for designing an RL-based solver for TSP, although Lisicki et al. (200 evaluated deterministic curricu- lum learning strategies on small TSP instances. For space reasons, our discussion below emphasizes the approaches using deep RL as a constructive heuristic (which builds a solution iteratively).
ments demonstrate the potential of machine-leaminn--aae
local search like
Invariance and equivariance have been important properties to exploit for designing powerful deep learning architectures (Bengio & Lecuu 1997, Gens & Domingos, 2014 Cohen & Welling 2016). They have also inspired some of the previous work on solving TSP problems, although they were often not explicitly discussed like in our work. For instance, Deudon et al.] (2018) use principal component analysis to exploit rotation invariance as a single preprocessing step. In contrast to their work, we compose various preprocessing transformations to be applied at every solving step. To the best of our knowledge, we are the first to propose such technique. In addition, permutation invariance is the motivation for using attention models (Kool et al. 2019 Deudon et al., 2018)) or GNNs (Mal al., 2019) in RL solvers. Contrary to Deudon et al. (2018). Kool et al. (2019) select the next city to visit based on the first and last visited cities while Ma et al. (2019) propose to use relative positions for translation invariance. Our proposition combines those two ideas, but compared to Kool et al. (2019), our model is based on GNN, while compared Ma et 20.1)) it has a simpler architecture that does not require an LSTM. For vehicle routing problems. et al. 2020) propose to remove visited cities from the RL agent's ' input, technique we also apply to TSP. In contrast to their work, our GNN model is simpler and we investigate generalization from small instances to very large instances. To summarize, compared to all previous work, our paper investigates in more systematic fashion the exploitation of equivariance to help training and improve generalization.
Several previous studies combine deep learning or RL with various local search techniques to find
better solutions: 2-opt (Deudon et al.) 2018 Ma et al., 2019; Da Costa et al., 2020 (w et al., 2021b), k-opt (Zheng et al. 2021), or Monte- Carlo tree search (Fu et al. 2021). In contrast to these methods, we use a combined local search technique, which applies several heuristics in an efficient way. Moreover, to the best of our knowledge, no previous work considers interleaving local search with policy gradient updates to obtain a more synergetic final method for solving TSP. For the bin packing problem. Cai et al. 2019 use RL to learn a perturbative heuristics to provide a good initial
2

---

Under review as a conference paper at ICLR 2022
solution to heuristic optimizer. Our interleaved training process is based on a similar idea, but our RL agent learns a constructive heuristics and we provide an intuitive motivation why this approach may work via our smoothed policy gradient.
All these machine-learning-basee based methods can be categorized as learning from a batch of instances directly learning on the instance be solved. Like our work, most methods are part of the first category. However, some recent work belongs to the second category (Zheng et al. 2021) or are hybrid (Fu et al. 202T). For instance, Zheng al. (2021) apply RL to make the LKH algorithm (Helsgaun 2017p, classic efficient heuristic for TSP, adaptive to the instance to be solved. In Fu al. (2021)'s s method, evaluations learned in a supervised way from batch of instances are used in Monte- Carlo tree search so that solutions can adaptively be found for the current instance. Being adaptive to the current instance can undoubtedly boost the performance of the solver. We leave for future work the improvement of our solver to become more adaptive to the instance to be solved.
PRELIMINARIES
Following previous work, we focus on the symmetric 2D Euclidean TSP, which we recall below. We then explain how a TSP instance can be tackled with RL. We first provide some notations:
For any positive integer N E N, []] denotes the set ( N). Vectors and matrices are denoted in bold (e.g., x X). For set of subscripts 1, X denotes the matrix formed by the rows of X whose indices are in I.
Traveling Salesman Problem A symmetric 2D Euclidean TSP instance is described by set of N cities (identified the set [N] and their coordinates in R22 The goal in this problem is to find the shortest tour that visits each city exactly once. The coordinates of city i are denoted æ; E IR?. The matrix whose rows correspond to city coordinates is denoted X Nx2, A feasible solution (i.e., tour) of TSP instance is a permutation a over [N] with length equal to:
Lo (X)
Σ Ir(()) Lo(tnill
where |1-I1a denotes the fz-norm, (1) E [N] is the 1-th visited city in tour a, and by abuse of notation, (N + 1) denotes (1). Therefore, solving a TSP instance consists in finding the permutation that minimizes the tour length La (X) defined in Equation (I). Since TSP solutions are invariant to scaling, we assume that the city coordinates are in the square [0, 1J². In Appendix A we recall some heuristics (e.g., insertion, k-opt) that have been proposed for solving TSP.
RL as a Constructive Heuristic RL can be used to construct a TSP tour a sequentially, Intu- itively, at iteration & E [N], RL solver (i.e., policy) selects the next unvisited city ott) to visit based on the current partial tour and the description of the TSP instance (i.c., coordinates cities). Therefore, this RI. problem corresponds
repeated N-horizon sequential decision-making prob- lem. As noticed by Kool et al.] (2019), the decision for the next city to visit only depends on the description of the TSP instance and the first and last visited cities. In addition, we update the de- scription of the TSP instance by removing the coordinates of visited cities. Surprisingly, to the best of our knowledge, no previous work exploits this simplified RL model.
Formally, in the RL language, at time step L E [N), an action represents the next city to visit, i.e., de = (t). Let 1 [N] and 4++1 = (L))) (t)} be the set of remaining cities after t cities have been already visited. Moreover, let J/ = [N] and J, = I, U (o(1), of unvisited cities addition of the first and last visited cities (a(1) and (t)). Therefore, a E I for all t. E [N]. A state 8; can be represented by a matrix X,, with flags indicating the first and last visited cities. This matrix includes the coordinates of unvisited cities (X,,) in addition to the coordinates of the first and last visited cities (I.(1) and (t)) Note that at t = 1, no city has been chosen yet, so the initial state $1 only contains the list of city coordinates. A state sy contains the coordinates of the unvisited cities and those of the first and last visited cities. After choosing the last city to visit in state s, the tour a is completely generated. The immediate reward r(st, a,) for an action de in state 8; can be defined as the negative length between the last visited city and the next
be the set
3

---

Under review as a conference paper at ICLR 2022
chosen city, since want the tour length to be small:
for
T (8t, 0z)
- 1|20011 (to(1-1)
for t ,,,.., N -
(2)
[[F) To(N 11 (2)ll
for / N
After choosing the first city 01 = a(1), the reward zero since no length can be computed. After the final action aN, additional reward- -1xx =>(NN) Il is added to complete the tour length.
In deep RL, a policy Te is represented as a neural network parametrized by O. The goal is then to find 0" that maximizes the objective function J(0):
N Σ T
0 arg max J(0) = arg max E po
0
0
where for all E [N]. r. = r(8,, 4)) T (81, (1, 82, 02 ...; 8N, aN) ) is a complete trajectory, and pe is the probability over trajectories induced by policy me. This objective function (()) can be optimized by a policy gradient (Williams) 1992) or actor-critic method (Sutton & Barto 1998).
4 EQUIVARIANT MODEL
In this section, we present several techniques to exploit invariances and equivariances in the design of an RL solver. Formally, mapping
A B from set A to a set B is invariant with respect to symmetry p : AA A iff f(z) = fo (x)) for any x E A. More generally, given a symmetry that acts A with م A - A and on B with p B B, mapping
A - B is equivariant with respect to this symmetry iff (f(((=)) = f() for any x E A. This definition shows that invariance is a special case of equivariance when of is the identity function. Intuitively, equivariance for an RL solver (resp. its value function) means that if a transformation is applied to its input, its output (resp. its value) can be recovered by a corresponding transformation.
In the remaining of the paper, for simplicity, we often use equivariance to refer to both equivariance and invariance, since the latter is special case of the former. Equivariance can be exploited in RL in various ways. We consider some equivariant preprocessing methods on the description of TSP instances to standardize the kinds of instances the solver trained on and evaluated on. In addition, propose a simple deep learning model for which we apply some other equivariant preprocessing methods on its inputs to further reduce the input space.
4.1 EQUIVARIANT PREPROCESSING OF TSP INSTANCE
An RL solver should be invariant with respect to any Euclidean symmetry (rotation, reflection, trans- lations and their compositions) and to any positive scaling transformation applied on city positions. To enforce these invariances, we can apply these transformations to preprocess the inputs of the solver such that the transformed inputs are always in a standard form. Doing so allows the solver to be trained more similar inputs.
Concretely, for rotation invariance, we rotate and scale the city positions such that they are mostly distributed along the first diagonal of the square [o, 1]2, This can be achieved by performing principal component analysis, rotating the first found axis by 45" anti-clockwise and scaling to fit the cities in the [0, 1 square. This transformation, which is slightly different from (Deudon al., 2018), allows the cities to be as spread as possible in [0. 1]2. For scaling and translation invariance, we apply scaling and translation transformation to the city positions such that there are a maximum number of cities (i.e., 2 or 3 depending on configuration) on the border of the square [0. 1j2. For reflections, we only consider horizontal, vertical, and diagonal flips (with respect to the coordinate axes) for simplicity. Cities are reflected such that a majority of them are in fixed chosen region.
Since the symmetries can be composed, these preprocessing methods can be applied sequentially. Theoretically, it would be beneficial to apply all of them in combination, however this has a com- putational cost. is therefore more effective to only use a selection the most effective ones. Moreover, these preprocessing methods can be applied either once on the initial TSP instance (X), or at each solving step on the remaining cities (X,.). Theoretically, performing these prepro- cessings iteratively should help most, since the RL. solver is only trained standardized inputs.
4

---

Under review as a conference paper at ICLR 2022
Encoder
Decoder
X
Preprocess
X
X
GNN
X
Ke(1)
X/.
Attertioon p
Xa(t)
Xeyty
MLP
F
X1,
Delete Kyrp
Xeio
Sampling
Xott)
Xj.1
Figure I: Model Architecture eMAGIC
This is confirmed by our experimental analysis. We find that the combination that provides the best results are rotation followed by scaling and translation, which will be used in the experimental evaluation of our method. However, our overall approach is generic and could include any other symmetries for which equivariance would hold for the RL solver. In Appendix F we present the details of the evaluation of the different preprocessing methods.
In the remaining, we assume that the set of equívariant transformations is fixed. For any set of in- dices 1 [VV, we denote the matrix of positions X after preprocessing by X, and any coordinates after preprocessing by ã. Note that the preprocessing step (e.g.. if it includes the rotation trans- formation described above) may depend on the initial matrix X,, but we prefer not to reflect it in the notations to keep them simple.
4.2 EQUIVARIANT MODEL
Our proposed model, which represents the RL solver, has an encoder-decoder architecture (see Fig- ure D.. In our model, the first city to visit is fixed arbitrarily, since the construction of the should be invariant to the starting city. Therefore, the decisions of the solver starts at time step t > 2. Our model designed take into account other equivariances that are known hold in the problem. Invariance with respect to translation can be further exploited by considering relative positions with respect to the last visited city instead of the original absolute positions, as suggested by Ma et al.) (019). Therefore, we define the input of our RL solver to only include two pieces of information. First, the information about the current partial tour now only needs the relative preprocessed position of the first visited city (# (1) Et)()). Since the last visited city is always represented by the origin, it can be dropped. Second, the information about the remaining TSP instance corresponds to the relative preprocessed positions of the unvisited cities (Æ Tn(n) Tt((t-1) for I,) and of the first and last visited cities (T)(1) and the origin (1) = 0). We denote the matrix of those
relative preprocessed positions by X,, i.e., the matrix whose rows are the rows X,, (obtained from X,) minus (.))) The last visited city needs to be kept in this matrix, since it represents the labels of the nodes of the remaining graph on which the tour should be completed.
Encoder With H denoting the embedding dimension, the encoder of our model is composed of graph neural network (GNN) (Battaglia al. 2018), which computes an embedding X,, R.I.Ix of the relative city positions X,, E x and a multilayer perceptron (MLP), which computes an embedding f E H of the relative position of the first visited city oo(1) E TR. The GNN encodes the information about the graph describing the remaining TSP problem. As GNN, it equivariant with respect to the order its inputs and its outputs depend on the graph structure and information (i.e., city positions). The MLP encodes the information about the first city. Since we exploit the independence with respect to the visited cities between the first and last cities (not included), model does not require any complex architecture, like LSTM (Hochreiter & Schmid- huber [197) or GNN, for encoding the positions of the visited cities, in contrast to most previous work. A simple MLP suffices since only the relative position of the first city is required.
5

---

Under review as a conference paper at ICLR 2022
Formally, the GNN computes its output X,, RR from inputs X J, E RI through GGNN layers, which allows each city to get information from its neighbors up to GIGNN edges away:
x (
(4)
X ((-11)
X 10 = X- X (1 + (1 F(O)
(5)
[Je]
where ( xxx and ( H are learnable weights, X (C-1) Rl is the input
of the eth layer of the GNN for & E [nNNN]] X (TONN) X,,, F(() : R| R| is the neural network, and parameter. Visual illustration of the GNN is deferred to Appendix H for space reasons.
aggregation function, which is implemented
[0, is another trainable
Decoder Once the embeddings X,, and Eo(0) are computed, the probability of selecting next city to visit is obtained via a standard attention mechanism (Bello et al. 2016 using X,, and (o) as the keys and query respectively. Formally, the decoder outputs vector EN expressed as:
Ej 4e otherwise
w tanh x O + + m
where u is the jth entry of the vector u, X i is the j"h row of the matrix X,,, Og and On trainable matrices with shape I x H. w E R. is another trainable weight vector. Then, softmax transformation turns u into a probability distribution p = (P)) JE(N) over unvisited cities:
e
softmax(u)
Σ j=m eni
JE[N]
where Pj is the 5thh entry of the probability distribution p and u, is the jth entry of the vector u. Note that the probability of any visited city Ie zero since u, = 00 in Equation (6
ALGORITHM & TRAINING
We introduce three innovative training techniques that we apply during our training process: com- bined local search, smoothed policy gradient, and stochastic curriculum learning. Overall, these techniques can help train a fast and generalizable policy, which able to generate tours that can easily be improved by local search. The overall Aggorithmccan be found in appendix C
Combined Local Search In contrast to previous work, which generally only considers 2-opt, we propose combination of several (possibly random) local search methods (i.e., local insertion heuristic, random 2-opt, search 2-opt and search random 3-opt) to improve a tour generated by the RL solver. For space reasons, defer their presentations in Appendix [A A local search method can heuristically improve a tour, but may get stuck in local optimum. Using a combination of them alleviates this issue, since different heuristics usually have different local optima. Another important distinction with previous work is that we also use local search during training, not only testing.
Smoothed Policy Gradient For simplicity, we train our model with the REINFORCE algorithm WWilliams 1992). which leverages the policy gradient for optimization. However, instead of using the standard policy gradient, which is based on the value of the tour generated by the policy, we compute the policy gradient with the value of the tour improved by combined local search. While standard RL training may yield policies whose outputs may not easily be improved by local search, our new definition directly trains the RL solver to find solutions that be improved by local search, which allows RI. and local search to have synergetic effects.
Intuitively, this new policy gradient amounts smoothing the objective function J(0) that is opti- mized. Recall (0) = LE [X), where the expectation is taken with respect to which is
Our implementation takes advantage of GPU acceleration when possible. The source code will be shared after nublication.

---

Under review as a conference paper at ICLR 2022
random variable corresponding to the tour generated by policy Te. In our approach, this usual objec- tive function is replaced by (+( (0) = L (X)], where 4+ is a random variable corresponding to the improved tour obtained by combined local search from σ. Therefore, this last expectation is taken with respect to the probability distributions generated by policy wo and our combined lo- cal search. This objective function can be understood as (+)
-E(ming'eN(o) T (X)] where (o)) is neighborhood of defined by local search. This stochastic min operation has smoothing effect on ((6). That is why, we call the gradient of J+ (0) a smoothed policy g gradient.
Formally, this novel policy gradient can be estimated on a batch of TSP instances (
(B);
B
1
Σ Ve log (ooa! ) (L.00(((0) -10))
Vo)+
B
where (0) is the tour generated by the current policy To on instance (()), a+
(b) is the improved
tour obtained by our combined local search starting from g(6), and ((6) LLa (x (6) is a novel baseline, which we call policy rollout baseline, used to reduce the variance of the policy gradi- ent estimation. It enjoys the nice property that does not require additional calculations, since Tu ( (x) computed when σ(6) is generated. our experiments, the policy rollout baseline easily outperforms the previous greedy baselines (Ma et al. [2019] Kool et al. 2019).
Therefore, the smoothed policy gradient updates more if our combined local search can make more improvements upon this certain policy. For completeness, we provide more details in Appendix B
Note that by construction, (_(x(x(()) (x( S (x
(b) E==1" ri
Stochastic Curriculum Learning Curriculum Learning (CL) widely used in machine learning (Soviany et al. (02T). Its basic principle is to control the increase of the difficulty of training instances. CL can speed up learning and improve generalization (Weinshall et al., 2018). We apply stochastic CL to train our model. Instead of a deterministic process, stochastic CL increases the difficulty according to a probability distribution. We choose the TSP size (i.e., number of cities) as measure of difficulty for a TSP instance. We assume it to be in the range of R = (1..,.....,5 For each epoch e, we define the vector ((())
E R-4 (since [R] = 41) to be:
(e) g
exp
ON
V2TON
where (e) is the k-th entry of (()) and hyperparameter n is the standard deviation of this Gaussian density function. Then, (e) is turned into categorical distribution p(*) E: [0, 1|41 via softmax:
p
softmax (e)
(10)
The k-th entry of (()) gives the probability of choosing a TSP instance of size (k + 10) at epoch e.
6 EXPERIMENTAL RESULTS
We present three sets of experiments. First, to validate the effectiveness of eMAGIC, we train our model on -ennomyyeeeeetteddd TSP instances (using stochastic CL with sizes up to 50), and test the model on other randomly-generater generated TSP instances (TSPn where size n = 20 up to 1000). Second, to further prove of its generalization capability, we directly evaluate models trained on random instances on realistic symmetric 2D Euclidean TSP instances with sizes range from 51 to 1002 in TSPLIB (Reineli) 1991). Third, we conduct an ablation study to show the significance of every component of eMAGIC (i.e., equivariance, stochastic CL, policy rollout baseline, combined local search, and RL). We evaluate four versions of our model: eMAGIC(G), eMAGIC(S), eMAGIC(s1) and eMAGIC(s10) where G means the tour is generated greedily from the RL policy, while the other ones are based on random sampling and differ with respect to the number of times eMAGIC is applied (once for s1, 10 times for s10 and 100 for S). The details about the experimental settings and the used hyperparameters, which are the same for all experiments, are provided in Appendix [
We compare the performance of our model with 12 other methods in Tables [ which covers various types of TSP solvers including exact solvers,
Performance on Randomly Generated TSP
7

---

Under review as a conference paper at ICLR 2022
Table I: Results of eMAGIC vs baselines, tested on 10,000 instances for TSP 20, 50 and 100.
Method
Type!
TSP20
TSP50
TSPI00
Len.
Gap
Time
Len.
Gap
Time
Len.
Gap
Time
Concorde
ES
3,830
0.00%
2.3m
5.691
0.00%
13m
7.761
0.00%
1.0h
Gurobi
ES
3.830
0.00%
2.3m
5.691
0.00%
26m
7.761
0.00%
3.6h
LKH3*
H
3.830
0.00%
21m
5.691
0.00%
27m
7.761
0.00%
50m
2-opt
H
4.082
6.56%
0.3s
6,444
13.24%
2.3s
9.100
17.26%
9.3s
Random
H
4.005
4.57%
3.3m
6,128
7.69%
12m
8.511
9.66%
17m
Farthest
H
3.932
2.64%
4.0m
6.010
5.62%
10m
8.360
7.71%
21m
GCN
SL(G)
3.855
0.65%
19s
5.893
3.56%
2.0m
8,413
8.40%
11m
GCN
SL(BS)
3.835
0.12%
21m
5.707
0.29%
35m
7.876
1.48%
32m
GCN
SL(BST)
3.831
0.01%
22m
5.692
0.03%
38m
7.872
1.43%
1.2h
A
SL+M
3.830
0.00%
1.6m
5.691
0.01%
7.9m
7.764
0.04%
15m
GAT
RL(S)
3.874
1.14%
10m
6.109
7.34%
20m
8.837
13.87%
48m
AM
RL(G)
3.841
0.29%
6.0s
5.785
1.66%
34s
8.101
4.38%
1.8m
AM
RL(S)
3,832
0.05%
17m
5.719
0.49%
23m
7.974
2.74%
1.2h
GPN
RL
4.074
6.35%
0.8s
6.059
6.47%
2.5s
8.885
14.49%
6.2s
MMAICCG) MMAIIC(S)
RL(LS)
3.841
0.29%
2.8s
5.732
0.74%
16s
7.923
2.09%
1,4m
RL(LS)
3.830
0.00 %
38s
5.691
0.01
3.5m
7.762
0.02%
14.6m
as reported in previous work. Random Random Insertion: Farthest Farthest Insertion.
JJshi et al. 2019a). 2 Fuu
2021). 8 Deudon al. 2018). (Kool et al. 2019). 5 (Ma et al. 2019)
ES Exact Solver; H Heuristie; SL Supervised Learning: RL Reinforcement Learning: G Greedy;
Sampling: M Monte- Carlo Tree Search; LS Combined Local Search; BS Beam Search; BST Beam
Search and Shortest Tour Heuristic.
Table 2: Results of eMAGIC vs baselines, tested on 10,000 instances for TSP 200, 500, and 1000.
Method
Type!
TSP200
TSP500
TSPI000
Len.
Gap
Time
Len.
Gap
Time
Len.
Gap
Time
Concorde*
ES
10.72
0.00%
3.4m
16.55
0.00%
38m
23.12
0.00%
7h
Gurobi
ES
LKH3*
H
10.72
0.00%
2.0m
16.55
0.00%
11m
23.12
0.00%
38m
2-opt
H
12.84
19.80%
34s
20.44
23.51%
3.3m
28.95
25.23%
14m
Random
H
11.84
10.47%
27s
18.59
12.34%
1.1m
26.12
12.98%
2.3m
Farthest
H
11.64
8.63%
33s
18.31
10.64%
1.4m
25.74
11.35%
2.9m
GCN+1
SL(G)
17.01
58.73%
59s
29.72
79.61%
7m
48.62
110.3%
29m
GCN+1
SL(BS)
16.19
51.02%
4.6m
30.37
83.55%
38m
51.26
122%
52m
GCN-1
SL(BST)
16.21
51.21%
4.0m
30.43
83.89%
31m
51.10
121%
3.2h
AGCRN+M*2
SL+M
10.81
0.88%
2.5m
16.97
2.54%
5.9m
23.86
3.22%
12m
G
RL(S)
13.18
22.91%
4.8m
28.63
73.03%
20m
50.30
117.6%
38m
*M
RL(G)
11.61
8.31%
5.0s
20.02
20.99%
1.5m
31.15
34.75%
3.2m
*M
RL(S)
11.45
6.82%
4.5m
22.64
36.84%
16m
42.80
85.15%
1.1h
GPN
RL
19.61
18.49%
28.47
23.15%
62o+2
RL+2opt
18.36
10.95%
26.13
13.02%
GPN
RL
13.28
23.87%
2.5s
23.64
42.87%
7.1s
37.85
63.72%
18s
MAGICCG))
RL(LS)
11.14
3.89%
36s
17.52
5.89%
2.0m
24.70
6.85%
4.9m
eMAGIC(S)
RL(LS)
10.77
0.50%
2.4m
17.03
2.92%
9.7m
24.13
4.36%
27m
See footnotes of Table
heuristics, and Harming-based approaches. Column and 2 of both Tables I and correspond to the method name and the method type. respectively. Columns 3, 4, and 5 provide the average tour length, gap to the optimal (provided by Concorde (Applegate et al. al, (004)), and computational time, respectively. For space reasons, only include results of eMAGICIG) and eMAGIC(S) in Tables
8

---

Under review as a conference paper at ICLR 2022
Table 3: Gap optimal for different ranges of instances in TSPLIB.
Size Range
eMAGIC(S)
Wu al.*1
S2VDQN22
OR
AM
1.20PT*5
Furthest
50 199
0.46%
15.00% 23.49%
3.77%
3.49%
78.73%
6.54%
7.60%
200 399
1.37%
6.87%
3.61%
293.76%
12.17%
9.54%
400
1002
3.40%
3.57%
10.11%
as reported in previous work.
1
(Wu et al.
2021a). 2 (Khalil al. 2017).
(Perron & Furnon).
Kool et al. 2019
(de O. da Costa
et al.
2020
(Furthest Insertion).
and 2 and leave results of other versions in Table Appendix E.1 Moreover, we provide the result variances for our methods and evaluate them on TSPI0,000 in resp. Appendices E.2 and E.3
Tandes[[and2] show that the computational times of exact solvers become prohibitive the TSP size increases. Note that Gurobi is not able to solve TSP instances larger than 200 under a reasonable time budget. The classic heuristic methods are relatively fast, but their performances are not satisfactory. Among all learning methods. Fu et al. (202T) provide excellent results, but it is based on Monte- Carlo tree search, which adapts to the instance to be solved. Without this adaptivity, our model with or without sampling provides competitive results. It can be better than Fu et al. (202T) up to TSP200. This somewhat suggests the limit of our approach, which trains on small instances and directly generalizes to large ones, without learning on the instance to be solved. We expect that our approach could be improved by training on slightly bigger instances (e.g., up to 100) or adding an adaptive component like in Fu al. (202I).
Performance on Realistic TSP Table 3 compares the performances of a variety of learning-based TSP solvers on instances from TSPLIB. Each column of Table 3 represents the average gap to the optimal solution over the instances indicated by the corresponding rows. We treat the tested instances as small instances if their sizes are under 200 and large instances otherwise. And we extend the testing to larger instances with size up to 1002 and leave the performances of other models as empty for size ranging from 400 to 1002 since their papers, the testings stop at instances with sizes around 400. We can observe from Table B that our model can perform much better than the other serming-based solvers not only for small problems but also large ones, which demonstrates the strong ability and the practical significance of eMAGIC to tackle realistic TSP problems. When the testing size increases, most models suffer from a relatively big increasing of the average gap while ours only increases less than 1% and remains in good absolute value (3.40%) for even larger instances, which indicates a strong generalization ability of our model. Further details and experimental results are provided in Appendix
Ablation Study We demonstrate the strength of all the techniques we applied (including equivari- ance, stochastic CL. policy rollout baseline, combined local search, and RL) using an ablation study. We turn off each feature one time to see if the performance drops compared to the full version of eMAGIC(s1). For space reasons, details of the ablation study are deferred to Appendix 10 and [I demonstrate that each technique plays role in our model.
Table
CONCLUSION
We presented a combination of novel techniques (notably, equivariance, combined local search, smoothed policy gradient) for designing an RL. solver for TSP, which shows good generalization capability. We demonstrated its effectiveness both on random and realistic instances, which shows that our model can reach state-of- thee----t----tttt performance.
For future work, the approach can be further improved in various ways, e.g., extending it to the actor-critic scheme and exploiting invariances with the critic; or making it adaptive and learn on the instance to be solved. The approach could also be applied on other combinatorial optimization problems and other RL problems.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
David Applegate, Bixby Ribert, Chvatal Vasek, and Cook William. Concorde tsp solver. 2004, URL
httt:::/ww.math
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals. Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks, 2018.
Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. CoRR, 2016.
Y. Bengio and Yann Lecun. Convolutional networks for images, speech, and time-series. 1997.
Qingpeng Cai, Will Hang, Azalia Mirhoseini, George Tucker, Jingtao Wang, and Wei Wei. Rein- forcement learning driven heuristic optimization. In DRI4KDD, 2019.
Taco S. Cohen and Max Welling. Group equívariant convolutional networks. In ICML, 2016. URL arXiv: 1602.07576.
http:// /ttp://aaxvv.//e org.org/////o.o httgg/bb//1602.0000 07576
Paulo R de Da Costa, Jason Rhuggenaath, Yinggian Zhang, and Alp Akeay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In ACMI, 2020.
Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning Combinatorial Optimization Algorithms over Graphs. Advances in Neural Information Processing Systems, DE- CEM2017:6349 6359, April 2017.
Paulo R. de O. da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning, 2020.
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis Martin Rousseau. Learning heuristics for the tsp by policy gradient. In CPAIOR, volume 10848 LNCS, pp. 170-181. Springer Verlag, 2018.
Vincent François-Lavet, Peter Henderson, Riashat Islam, Marc G. Bellemare, and Joelle Pineau. An introduction to deep reinforcement learning. Foundations and Trends in Machine Learning, 11 (3-4), 2018
2018.
Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large TSP instances. In AAAI, 2021.
Robert Gens and Pedro M Domingos. Deep symmetry networks. In NeurlPS, 2014.
Sabih H. Gerez, Algorithms for VLSI Design Automation, chapter Routing. Wiley, 1999.
Keld Helsgaun. An extension of the seemighan-helsgare tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 2017.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9()): 1735-1780, 1997.
Neil Jones and Pavel A. Pevzner. An Introduction to Bioinformatics Algorithms. MIT Press, 2004.
Chaitanya K. Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. CoRR, 2019a.
Chaitanya Joshi, Thomas Laurent, and Xavier Bresson. On learning paradigms for the travelling salesman problem. In NewrlPS 2019 Graph Representation Learning Workshop, 2019b.
10

---

Under review as a conference paper at ICLR 2022
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. In I. Guyon, U. V. Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL
ngs neur iisuurpps... pss.... .c/
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems!, 2019.
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning, 2021.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial Optimization with Graph Convolu- tional Networks and Guided Tree Search. In Advances in Neural Information Processing Systems, volume 2018-Decem, pp. 539-548, 2018. URL httl:tttpp///iiiiee wwt. wttrg//bs/1811...0 10659
Michal Lisicki, Arash Afkanpour, and Graham W. Taylor. Evaluating curriculum learning strategies in neural combinatorial optimization, 2020.
Qiang Ma. Suwen Ge. Danyang He, Darshan Thaker, and Iddo Drori. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. CoRR, 2019.
Christos H. Papadimitriou. The euclidean travelling salesman problem is np-complete. Theoretical Computer Science, 4(3):237-244) 1977.
Bo Peng, Jiahai Wang, and Zizhen Zhang. A Deep Reinforcement Learning Algorithm Using Dy- namic Attention Model for Vehicle Routing Problems. In Kangshun Li, Wei Li, Hui Wang, and Yong Liu (eds.), Artificial Intelligence Algorithms and Applications, Communications in Com- puter and Information Science, pp. 636-650, Singapore, 2020. Springer. ISBN 9789811555770. doi: 11110079778-911-5-55777777
51.
Laurent Perron and Vincent Furnon. Or-tools. URL htt.psss/ddeeelleesss.oooo wwwp::elloprrr.gglle....o com/
optimi zon/
Marcelo O. R. Prates, Pedro H. Avelar, Henrique Lemos, Luis Lamb, and Moshe Vardi. Learning to solve np-complete problems graph neural network for decision tsp. In AAAI, 2019, URL
httt:://arxis wwt.wbs////aaooee. /1t/..11...0 118.9.020091111
Gerhard Reinelt. TSPLIB-a traveling salesman problem library. ORSA Journal on Computing, (4):376-384, 1991.
L.V. Snyder and Z.-J.M. Shen. Fundamentals of Supply Chain Theory, chapter The Traveling Sales- man Problem, pp. 403-461, Wiley, 2019.
Petru Soviany, Radu Tudor Ionescu, Paolo Rota, and Nicu Sebe. Curriculum learning: A survey, 2021.
R.S. Sutton and A.G. Barto. Reinforcement learning: An introduction. MIT Press, 1998.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In NIPS, pp. 2692-2700, 2015.
Daphna Weinshall, Gad Cohen, and Dan Amir. Curriculum learning by transfer learning: Theory and experiments with deep networks. In ICML, 2018.
Ronald J. Williams. Simple statistical following algorithms for connectionistreiifooceeee learning. Machine Learning, pp. 229-256, 1992.
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, pp. 1-13, 2021a. doi: 10. 1.11109/NNISS.0222 2021.308888..
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuris- tics for solving the travelling salesman problem. IEEE Transactions on Neural Networks and Learning Systems, 2021b.
11

---

Under review as a conference paper at ICLR 2022
Zhihao Xing and Shikui Tu. A graph neural network assisted monte carlo tree search approach to traveling salesman problem. IEEE Access, 8:108418-108423 2020. doi: 10.1109/ACCESS. 2020.3000236.
Jiongzhi Zheng, Kun He, Jianrong Zhou, Yan Jin, and Chu-Min Li. Combining reinforcement learning with sin-Kermighan-Heessau algorithm for the traveling salesman problem. In AAAI, 2021.
12

---

Under review as a conference paper at ICLR 2022
A COMBINED LOCAL SEARCH
We first provide a brief introduction to TSP heuristics and then give the detailed presentation of each local search method we used, together with our whole combined local search algorithm.
Since TSP is an NP-hard problem (Papadimitriou 1977). solving exactly large TSP instances is generally impractical. Hence, many heuristics have been proposed solve TSP. Two important categories of heuristics are constructive heuristics and local search heuristics. On the one hand, constructive heuristics iteratively build a tour from scratch and therefore, do not rely on existing tours. As an example, insertion heuristics are constructive: they first choose starting city randomly, then repeatedly insert an unvisited city into the partial tour that minimizes the increase of tour length until all the cities are included in the tour. The unvisited city can be selected in different ways leading to various versions of insertion heuristies: random insertion, nearest insertion, or farthest insertion (see Kool et al. (2019) for implementation details). Among them, farthest insertion usually yields the best results. On the other hand, local search heuristics try to improve a given complete tour by perturbing it. They are widely used as post optimization for TSP solvers, such as Deudon et al. (018);; Ma et al. (2019). One important class of local search heuristic is k-opt, which improves an existing complete tour by repeatedly performing the following operation: remove h edges of the current tour and reconnect the obtained subtours in order to decrease the tour length. For instance, one 2-opt operation would replace:
o = (2)(), 0(1) o())...,
by
o' d'= (o1),,,. -0) 1), ai 1), aj + 1),, 1),....((NN) where i <j < if (X) < L, (X). Based on k-opt, the LKH algorithm (Helsgaun, 2017 can often achieve nearly optimal solutions, but requires long runtime.
Based on how many edges are removed and how the subtours are reconnected during one step, every local search heuristic can be seen as a special case of k-opt. Since the number of possible k-opt operations is O(N*), 2-opt and 3-opt are usually preferred to efficiently search for fast improve- ments of existing tours, although they can get stuck in local optima. Hence, in our work, we use a combination of several local search methods, including local insertion heuristics, random 2-opt, search 2-opt, and search random 3-opt (see below for their definitions), to efficiently find potential 2-opt and 3-opt operations to improve the solution proposed by the RI. solver. Instead of running each algorithm once for long enough, we run every local search shortly one by one and repeat this process for multiple times so that the combined local search are able avoid more local optima. Intuitively, the rationale is that once a certain heuristic gets stuck in a local optimum, another can help get it out by trying a different operation. Next, explain the above four heuristies, and then illustrate how we leverage them to form our combined local search.
A.1 RANDOM 2-OPT
For random 2-opt, we randomly try two edges for performing 2-opt operation and repeat this process for a x 2 times, where a, 3 > O are two hyperparameters controlling the strength of this heuristic as well as its runtime. Theoretically, random 2-opt can potentially cover all 2-opt operations and such procedure makes random 2-opt much more flexible than trying all N(N - 1)/2 possible pairs of edges. this paper, we set a = 0.5 and 1.5 for all experiments.
A.2 LOCAL INSERTION HEURISTIC
For local insertion heuristic, inspired by the insertion heuristic, we iterate through all cities and find the best positions to insert them from their original locations. Let a be the current tour and ofe be the tour where we exchange the positions of a (l) with a (L'). Namely,
t,, (o(1), (t'), (t), (t' + +), alt - 1), att + +1)...,,(NN)
(11)
for L' + - and -t = a. The local insertion heuristic (see Algorithm iterates over every t [N]. For each f, we need find such that:
= arg min La (X),
(12)
13

---

Under review as a conference paper at ICLR 2022
where the definition of L is given in Equation ① Then replace by dr. Theoretically, the local insertion heuristic a special case of 3-opt where two of the removed edges cover a same node.
Algorithm Local Insertion Heuristic
1: Input: A matrix of city coordinates X (2:) current tour o
2: Output: An improved tour
3: for t = to N do
4: t" = arg mine Lo (X)
5: σ d2.1"
6: end for
7: return
A.3 SEARCH 2-OPT
For search 2-opt, we first iterate through all edges and for each first edge, we search for the best second edge to do the 2-opt. Let a be the current tour and (t,r)) be the tour where we reverse the cities between (t) and (t'). Namely,
((.ee) (o(1), - 1), ()), 1), .., o(l (1)
(13)
where < f', and (t.)) a. Search 2-opt (see Algorithm 2 iterates over every [N]. For each i, we find /* such that:
1" = arg min La (X)
(14)
Pzt
Then we replace by (1,r)) Search 2-opt potentially covers all possible 2-opt operations.
Algorithm 2 Search 2-opt
1: Input: matrix of city coordinates X (2;))E(N)) current tour o
2: Output: An improved tour
3: for 1 to do
4: t" arg mi (X)
5: σ + (t.r))
6: end for
7: return
A.4 SEARCH RANDOM 3-OPT
For search random 3-opt, the algorithm first randomly picks two edges. Then for these two randomly-picked edges, similar to search 2-opt, we search to find the best third edge to apply 3- opt. Let be the current tour, edges from (41) to (11 + 1) and (t22) to a 1) be the two randomly picked edges and (11.22.5) be the optimal tour that differs from a only in edges from (t2)) at, + 1). (t2) to (t2 + 1) and (tss) to or (ts + 1). For randomly picked and t2, search random 3-opt (see Algorithm 3) iterates over every ta E [N] and find to such that:
t arg min Lyn
(2:tg) (X)
(15)
We repeat this process for N times, where a, B 0 are the same two hyperparameters in random 2-opt. We set a = 0.5, B = 1.5 for all experiments. Search random 3-opt potentially covers all possible 3-opt operation.
A.5 COMBINED LOCAL SEARCH
With these 4 different local search heuristics, combined local search applies them one by one sequentially and repeat this for times (see Algorithm 4), where a hyperparameter, which we set to I = 10 for all experiments in this paper.
14

---

Under review as a conference paper at ICLR 2022
Algorithm 3 Search random 3-opt
1: Input: matrix of city coordinates X (2t)ie(N)) current tour o, hyperparameters a and /
2: Output: An improved tour
3: for iter= 1 to aN8 do
4: Randomly pick t2 [N] such that t + t2
5: t/ arg min; ( (X)
6:
7: end for
8: return
Algorithm 4 Combined Local Search Algorithm
Input: A matrix of city coordinates X (Ii)ae[N), current a, hyperparameters a, 3 and I for local search.
2: Output: An improved tour
3: for t 1 to I do
4: о f apply local insertion heuristic o)) apply random 2-opt on for oN times
5:
6: a f apply search 2-opt on
7:
apply search random 3-opt for aN times
8: end for
9: return
B POLICY GRADIENT OF EMAGIC
As promised in Section Smoothed Policy Gradient, we elaborate the detailed mathematical derivation for Equation
The objective function ((O) in Equation be approximated with the empirical mean of the total rewards using B trajectories sampled with policy πe:
N
B
N
J(0) = La
En
Σ
(16)
B
where Ëg represents the empirical mean operator, Lo (X) is the tour length of output by the RL policy and (!6 the reward of the b-th trajectory. The policy gradient to optimize [() can be estimated by:
N
N
VoJ(O) = -E,
Vo log To(a))s))
Σ
(17)
2 BB
Vo log ~o (a
18 (b)
(b)
(6)
However, Recall .(00) is the standard objective used in most deep RL methods applied to TSP. Instead, optimize J (0) -ELLo, (X)] where Lo, (X) is the tour length of after applying local search. This helps integrate better RL and local search by smoothing the value landscape and training an RL agent output a tour that can be improved by local search. This new objective function can be rewritten:
J+(() = -Ea - (X))
(18)
= Egato [Ba (To, (X), (X)
15

---

Under review as a conference paper at ICLR 2022
where p(a) denotes the distribution over tours induced by the application of the stochastic local
search on σ. Taking the gradient this new objective:
VoJ+ (0) -Er
Vo log mo(aalls)) Eo, Nolo (X)1a)
Ve log (a (aaa/1111 (111)))) ( (L (1opo(2(01)
23 EB
(19)
1
Vo log Tola, loaaa! (0) (x
where 7 = (81, . and is its associated tour. We simply approximate the conditional expecta- tion over p(ar) by a sample. Therefore, our gradient estimate is an unbiased estimator of the gradient of our new objective J (0).
Using our policy rollout baseline introduces some bias to the estimation of the smoothed policy gradient. However, the variance reduction helps with achieving greater performance and smaller variance, as we observed in our experiments.
C OVERALL ALGORITHM
We provide the pseudo-code of overall training algorithm in Algorithm
Algorithm 5 REINFORCE exploiting stochastic CL., equivariance, and smoothed policy gradient
1: Input: Total number of epochs E, training steps per epoch T, batch size B, hyperparameters a,
B. 7 and for local search
2: Initialize 0
to E do 4: N Sample from pl1) according to Stochastic CL
3: for
5: for t = to do
6:
vb {1,..., B} (b)
Random TSP instance with N cities
7:
vb (1,.., g (b)
Apply no on (b) after all the equivariant preprocessing steps
8:
vb E (1, (1,.., B)
Apply the combined local search (+)
9:
Use o (b) and _h) to calculate V Vo.+(()) according to Equation 8
10:
f t Update in the direction of (o.+(())
11: end for
12:
end for
D SETTINGS AND HYPERPARAMETERS
All our experiments are run on computer with an Intel(R) Xeon(R) E5-2678 v3 CPU and NVIDIA 1080Ti GPU. In consistency with previous work, all our randomly generated TSP instances sam- pled in [o, 1 uniformly. During training, stochastic CL chooses TSP size in R (10, 11,...,50 50} for each epoch according to Equations (9) and (IO). with O, set to be 3. We trained for 200 epochs in each experiment, with 1000 batches of T28 random TSP instances in each epoch. We set the learn- ing rate to be 10 and the learning rate decay to be 0.96 in each experiment. In each experiment, we set = 0.5, 3 = 1.5, 7 0.25 and / = 10 for the parameters of our combined local search; As for random TSP testing and the ablation study, we test on TSP instances with size 20, 50, 100, 200, 500 and 1000 to evaluate the generalization capability of our model; for realistic TSP, we test TSP instances with sizes up to 1002 from the TSPLIB library. With respect to our model architecture, our MLP encoder has an input layer with dimension 2, two hidden layers with dimension 128 and 256, respectively, and an output layers with dimension 128; for the GNN encoder. we set 128 and NGNN 3.
16

---

Under review as a conference paper at ICLR 2022
E MORE EXPERIMENTS ON EMAGIC
E. 1
MORE VERSIONS OF EMAGIC
As promised in Section 6
illustrate all versions of eMAGIC in this section:
Table 4: Results of eMAGIC vs baselines, tested on 10,000 instances for TSP 20, 50, and 100.
Method
Typet
TSP20
TSP50
TSP100
Len.
Gap
Time
Len.
Gap
Time
Len.
Gap
Time
eMAGIC(G)
RL(LS)
3.841
0.29%
2.8s
5.732
0.74%
16s
7.923
2.09%
1.4m
eMAGIC(sI)
RL(LS)
3.844
0.37%
3.0s
5.763
1.27%
17s
7.964
2.61%
1.3m
MAGIC(S1
RL(LS)
3.831
0.03%
9.0s
5.728
0.67%
49s
7.852
1.17%
2.9m
MMAIIC(S)
RL(LS)
3.830
0.00% %
38s
5.691
0.01 %
3.5m
7.762
0.02%
14.6m
Greedily generate a solution from RI. policy and improve by combined local search.
sl: Randomly sample only one solution from the RI. policy and improve it by combined local search.
s10: Randomly sample 10 solutions from the RL policy and improve them by combined local search. Finally, keep the best tour.
Randomly sample 100 solutions from the policy improve by combined local search. Finally,
keep the best tour.
Table 5: Results of all versions of cMAGIC, tested on 128 instances for TSP 200, 500, and 1000.
Method
Type
TSP200
TSP500
TSP1000
Len.
Gap
Time
Len.
Gap
Time
Len.
Gap
Time
e.MAII((G)
RL(LS)
11.14
3.89%
36s
17.52
5.89%
2.0m
24.702
6.85%
4.9m
eMAGIC(s1)
RL(LS)
11.14
3.89%
34s
17.54
6.07%
1.8m
24.749
7.05%
4.9m
IMAGIC(S10)
RL(LS)
10.95
2.12%
1.1m
17.29
4.50%
4.1m
24.503
5.99%
11m
eMAGIC(S)
RL(LS)
10.77
0.50%
2.4m
17.03
2.92%
9.7m
24.126
4.36%
27m
See footnotes of Table
E.2 VARIANCE ANALYSIS OF EMAGIC
we provide the variance analysis of eMAGIC in this section. In our experiments, we repeated all our experiments (training + testing) with 3 random seeds. The variances are shown below:
As promised in Section 0
Table 6: Variance Analysis of eMAGIC
Model
TSP20
TSP50
TSP100
TSP200
TSP500
TSP1000
eMAGIC(G)
0.043
0.049
0.050
0.064
0.056
0.066
eMAGIC(sI)
0.0413
0.0407
0.0509
0.0510
0.0553
0.0655
eMAGIC(s10)
0.0446
0.0486
0.0434
0.0679
0.0652
0.0713
eMAGIC(S) 0.0478
0.0582
0.0680
0.1207
0.1288
0.1742
See footnotes of Table
The variances are quite low, showing that our method gives relatively good and stable results. Note the variances increase with the number of sampling (s1, s10 and S) for larger TSP instances since there is more room for improvement.
E.3 EXPERIMENTS ON EXTREMELY LARGE TSP INSTANCES
In Table show the performances of eMAGIC extremely large TSP instances (i.e., TSP 10,000) and the comparisons with a few methods that are able to generalize to TSP 10,000, For the hyperparameters of the combined local search, use / = and B 1.4. We modify the
17

---

Under review as a conference paper at ICLR 2022
hyperparameters in this way because find that for large TSP instances, doing too many iterations of local search is not efficient. The other experimental settings this test are the same as Section 6
Also, we test Fu et al. 20210's method with a limited the time budget, denoted by AGCRN+M
since we only reproduce their method successfully with CPU, we decrease their hyperparameter T (the MCTS will end no longer than T seconds) from 0.04n 0.04n /18 (28/ /60) 0.010n (1.8h and 28m are respectively the runtimes of their model and eMAGIC(G)) By this, we expect that their model and eMAGIC(G) will have similar running time.
Table 7: Results of eMAGIC baselines, tested on 16 instances for TSP 10,000.
Method
Type?
TSP 10,000
Len.
Gap (to LKH3)
Time
LKH3*
Heuristic
70.78
0.00%
8.8h
AM
RL(S)
431.6
501 %
13m
AM
RL(G)
141.7
97.4%
6.0m
AM
RL(BS)
129.4
80.3%
1.8h
SL+M
74.92
4.39%
1.8h
AGCRN+M tim
SL+M
80.11
13.2%
eMAGIC(G) eMAGIC(S)
RL(LS)
79.28
10.5%
28m
RL(LS)
78.79
9.76%
1.0h
as reported in previous work.
2 Fu et al. [2021 4 Kool et al. 2019
Jnw with a time budget
HH Heuristic; SL Supervised Learning: RL- Reinfforeeeet Learning: G Greedy; S Sampling: M
Monte-Carlo Tree Search; LS Combined Local Search; BS Beam Search.
We can observe that our models outperform AM Kool et al. 2019 large extent. Comparing
to AGCRN+M (Fu et al. 202Tb and LKH3 (Helsgaun 2017 our methods run much faster without big gap of performance. Plus, if we give AGCRN+M Fuu al.
202T time budget comparable
to our method (i.e., run AGCRN+M and eMAGIC(G) for the same amount of time), we can see that our algorithm outperforms AGCRN+M. Note that MCTS in AGCRN+M written in C++. We could reduce our runtime if we had also written our code in C++ instead of Python. Therefore, our method offers a better trade-off in terms performance vs runtime: it can generate relatively good results in much less time.
F EVALUATION OF EQUIVARIANT PREPROCESSING METHODS
F.1 COMPARISONS BETWEEN DIFFERENT SYMMETRIES USED DURING PREPROCESSING
We present the comparison results of applying rotation, translation and reflection. The comparisons are done by testing on random TSP instances followed the same setting in the experiment section. As in table g the rotation has the best performance on small and large TSP instances. By this, we choose rotation for our final algorithm.
Table 8: Comparisons between rotation, translation and reflection
TSP Size
Rotation
Reflection
Translation
Len.
Gap
Len.
Gap
Len.
Gap
TSP 20
3.844
0.37 %
3.850
0.51%
3.848
0.47%
TSP 50
5.763
1.27% %
5.786
1.67%
5.807
2.05%
TSP 100
7.964
2.61 %
8.050
3.72%
8.020
3.33%
TSP 200
11.14
3.89 %
11.22
4.71%
11.19
4.30%
TSP 500
17.54
6.01 %
17.65
6.69%
17.68
6.85%
TSP 1000
24.75
7.05%
24.81
7.33%
24.86
7.55%
18

---

Under review as a conference paper at ICLR 2022
F.2 COMPARISONS BETWEEN ONE PREPROCESSING APPLICATION AND ITERATION PREPROCESSING APPLICATIONS
We present the comparison results of preprocessing application and iteration preprocessing ap- plications. The comparisons are done by testing on random TSP instances followed the same setting the experiment section. As in table 9 the iteration preprocessing applications has better perfor- mance on small and large TSP instances. By this, we choose iteration preprocessing applications for our final algorithm.
Table 9: Comparisons between iteration preprocessing and one preprocessing
TSP Size
Iteration
One
Len.
Gap
Len.
Gap
TSP 20
3.844
0.37%
3.873
1.12%
TSP 50
5.763
1.27%
5.871
3.17%
TSP 100
7.964
2.61%
8.102
4.40%
TSP 200
11.136
3.89%
11.347
5.85%
TSP 500
17.541
6.01%
17.742
7.23%
TSP 1000
24.749
7.05%
24.978
8.05%
Iteration preprocessing application.
# Once preprocessing application.
G ABLATION STUDIES
This section illustrates the details of Section 6 Ablation Study.
G.1 ABLATION STUDY ON KEY TRAINING TECHNIQUES
In this section, as promised in Section 6 Ablation Study, we will illustrate the details the ablation study regarding some key training techniques of eMAGIC. For equivariance, we remove all the cquivariant procedures during training/testing (c.g., deleting visited cities, preprocessing, and using relative positions). For the policy rollout baseline, replace it with the self-critic baseline, which a greedy baseline implemented in Ma et al. (2019). For combined local search, we only apply it during testing to check if it can help improve the training process. For RL, directly apply combined local search without performing any learning. Table 10 demonstrates that each technique plays role in our model.
Table 10: Ablation study equivariance, policy rollout baseline, combined local search, and RL, tested on 10,000 instances for TSP 20, 50 and 100, and 128 instances for TSP 200, 500 and 1000.
TSP Size
Full
w/o Equiv.
w/o BL
w/o LSE
w/o RL
Len.
Gap
Len.
Gap
Len.
Gap
Len.
Gap
Len.
Gap
TSP20
3.844
0.37 %
3.857
0.69%
3.875
1.17%
3.874
1.15%
3.879
1.27%
TSP50
5.763
1.27
5,808
2.07%
5.859
2.96%
5.837
2.58%
5.901
3.70%
TSP100
7.964
2.61% %
8.086
4.19%
8.124
4.68%
8.100
4.37%
8.178
5.38%
TSP200
11.14
3.89%
11.27
5.16%
11.33
5.71%
11.32
5.64%
11.43
6.67%
TSP500
17.54
6.01 %
17.72
7.10%
17.74
7.22%
17.82
7.71%
17.86
7.96%
TSP1000
24.75
7.05% %
24.94
7.86%
24.99
8.10%
25.12
8.67%
25.15
8.80%
Equiv. equivariance; BL Baseline; LS Combined Local Search.
G.2 ABLATION STUDY ON OTHER TRAINING TECHNIQUES
In this section, first perform ablation study of stochastic CL, meaning fixed our TSP size to be 50 during training. Moreover, we perform an ablation study on each component of our equiv- alent model, which includes deleting the visited cities during training, equivariant preprocessing
19

---

Under review as a conference paper at ICLR 2022
operation, and using relative positions during training, mentioned in Section 6 Ablation Study- For the ablation study of these three components, we remove them during training and testing. Ta- ble IT fillustraaes the results of our ablation study (including the full version for comparison), which demonstrate that each component effective our model.
Table 11: Ablation study on stochastic CI., Deleting, Preprocessing and Relative Position, tested on 10,000 instances for TSP 20, 50 and 100, and 128 instances for TSP 200, 500 and 1000.
TSP Size
Full
w/o CL.
w/o Delete
w/o Pref
w/o RP
Len.
Gap
Len.
Gap
Len.
Gap
Len.
Gap
Len.
Gap
TSP20
3.844
0.37 %
3.861
0.79%
3.855
0.66%
3.855
0.64%
3.852
0.57%
TSP50
5.763
1.27 %
5.821
2.30%
5.824
2.34%
5.811
2.11%
5.823
2.33%
TSP100
7.964
2.61% %
8.062
3.88%
8.064
3.90%
8.084
4.16%
8.093
4.28%
TSP200
11.14
3
11.29
5.29%
11.28
5.18%
11.27
5.17%
11.30
5.44%
TSP500
17.54
6.01 %
17.69
6.93%
17.67
6.80%
17.68
6.85%
17.72
7.07%
TSP1000
24.75
7.05 %
24.89
7.68%
24.88
7.63%
24.88
7.63%
24.89
7.66%
Pre Preprocessing; RP Relative Position.
G.3 COMPARING PURE RL ALGORITIM WITH FULL ALGORITIM
when doing the ablation study for the combined local search, we do not apply it during training. but we still apply during testing check if it can help improve the training process. Here, we compare the pure RL algorithm (full algorithm without local search both in training and testing) and the full algorithm demonstrate the strength Combined Local Search:
In Section 6
Table 12: Comparisons between pure RL algorithm and the full algorithm
TSP Size
Full
Pure RL
Len.
Gap
Len.
Gap
TSP 20
3.844
0.37 %
3.874
1.14%
TSP 50
5.763
1.27%
6.172
8.46%
TSP 100
7.964
2.61% %
8.688
12.0%
TSP 200
11.136
3.89%
12.19
13.7%
TSP 500
17.541
6.01 %
19.31
16.7%
TSP 1000
24.749
7.05%
27.10
17.2%
20

---

Under review as a conference paper at ICLR 2022
H GNN ENCODER DETAILS
Figure 2 is a detailed illustration of the GNN architecture introduced in Section Please notice that Figure 2 could be regarded as a zoom-in version of the GNN part Figure The aggregation function used in GNN is represented by a neutral network followed by a ReLU function on each entry of the output.
Linear,
X
Linear,
x Ansan
Linear, 2
Aggregation
x(1- 2n)
Aggregation
Aggregation
Ancon?
X"Neex = 8,
Figure 2: Detailed Architecture of GNN
I REALIST TSP INSTANCES IN TSPLIB
As promised in Section Tables 14 to 16 list the performances various learning-based TSP solvers and heuristic approaches upon realistic TSP instances in TSPLIB. The bold numbers show the best performance among all the approaches. We can observe that most bold numbers are provided by eMAGIC, meaning our approach provides excellent results for TSPLIB. In addition, we also provide our results for the larger instances (with size up to 1002) from TSPLIB in Table T3 Table 13 only contains the experiments of our model since no other model can generalize to large size TSP instances with adequate performance.
Table 13: Comparison of Performance on large size TSP instances in TSPLIB
Problems
OPT
eMAGIC(S)
Tools
Furthest Insertion
Length
Gap
Length
Gap
Length
Gap
rd400
15,281
15,707
2.79%
15,821
3.53%
16,851
10.00%
f1417
11,861
11,961
0.84%
11,996
1.14%
12,845
8.23%
pr439
107,217
109,610
2.23%
117,171
9.28%
121,341
12.89%
pcb442
50,778
51,868
2.15%
52,508
3.41%
57.741
13.42%
d493
35,002
36,184
3.38%
36.599
4.56%
38,869
10.69%
u574
36,905
38,486
4.28%
38,467
4.23%
40,570
9.562%
rat575
6,773
7.105
4.90%
6,851
1.15%
7,632
12,
p654
34,643
35,001
1.03%
35.199
1.60%
35,706
3.04%
d657
48,912
50,826
3.91%
50,585
3.42%
53,796
9.61%
u724
41,910
43,853
4.64%
43,585
4.00%
46,367
10.16%
rat783
8,806
9,324
5.88%
8,974
1.91%
9,904
11.78%
pr1002
259,045
271,370
4.76%
271,095
4.65%
285.797
9.86%
21

---

Under review as a conference paper at ICLR 2022
Table 14: Comparison of Performances on TSPLIB Part I
Problems
OPT
eMAGIC(S)
Wu al.'
S2V-DQN
Len.
Gap
Len.
Gap
Len.
Gap
ei151
426
429
0.70%
438
2.82%
439
3.05%
berlin52
7,542
7,544
0.03%
8,020
6.34%
7,542
0.00%
st70
675
677
0.30
706
4.59%
696
3.11%
ei176
538
546
1.49 %
575
6.88%
564
4.83%
pr76
108,159
108,159
0.00%
109,668
1.40%
108,446
0.27%
rat99
1,211
1,223
0.99% %
1,419
17.18%
1,280
5.70%
kroA 100
21,282
21,285
0.01 %
25,196
18.39%
21,897
2.89%
kroB100
22,141
22,141
0.00 %
26,563
19.97%
22.692
2.49%
kroC100
20,749
20,749
0.00 %
25,343
22.14%
21,074
1.57%
kroD100
21,294
21,361
0.31
24,771
16.33%
22,102
3.79%
kroE100
22,068
22,068
0.00 %
26,903
21.91%
22,913
3.83%
rd100
7,910
7916
0.08%
7,915
0.06%
8,159
3.15%
eil101
629
636
1.11%
658
4.61%
659
4.77%
lin105
14,379
14,379
0.00
18,194
26.53%
15,023
4.48%
pr107
44,303
44,346
0.10% %
53,056
19.76%
45,113
1.83%
pr124
59,030
59,075
0.08% %
66,010
11.82%
61,623
4.39%
bier127
118,282
119,151
0.73%
142,707
20.65%
121,576
2.78%
ch130
6,110
6,162
0.85% %
7,120
16.53%
6,270
2.62%
pr136
96,772
97,264
0.51% %
105,618
9.14%
99.474
2.79%
pr144
58,537
58,537
0.00 %
71,006
21.30%
59,436
1.54%
ch150
6,528
6,592
0.98%
7,916
21.26%
6,985
7.00%
troA150
26,524
26,727
0.77% %
31,244
17.80%
27,888
5.14%
kroB 150
26,130
26,282
0.58%
31,407
20.20%
27,209
4.13%
pr152
73,682
73,682
%
85,616
16.20%
75,283
2.17%
u159
42,080
42,080
0.00%
51,327
21.97%
45,433
7.97%
rat195
2,323
2,377
2.32%
2,913
25.40%
2,581
11.11%
d198
15,780
15,874
0.60%
17,962
13.83%
16,453
4.26%
kroA200
29,368
29,840
1.61 %
35,958
22.44%
30,965
5.44%
kroB200
29,437
29,743
1.04%
36,412
23.69%
31,692
7.66%
ts225
126,643
126,939
0.23%
158,748
25.35%
136.302
7.63%
tsp225
3,916
3,981
1.66%
4,701
20.05%
4,154
6.08%
pr226
80,369
80,436
0.08%
97,348
21.13%
81,873
1.87%
gi g21262
2,378
2,417
1.64%
2,963
24.60%
2,537
6.69%
pr264
49.135
49,908
1.57% %
65,946
34.21%
52,364
6.57%
a280
2,579
2,635
2.17%
2,989
15.90%
2,867
11.17%
pr299
48,191
48,905
1.48%
59,786
24.06%
51,895
7.69%
lin318
42,029
42,948
2.19%
45,375
7.96%
as reported in previous work.
et al. 2021a),
Khalil et al.
2017
22

---

Under review as a conference paper at ICLR 2022
Table 15: Comparison of Performances on TSPLIB Part II
Problems
OPT
L2OPT*
AM
Furthest
Len.
Gap
Len.
Gap
Len.
Gap
ei151
426
427
0.23%
435
2.11%
467
9.62%
berlin52
7,542
7,974
5.73%
7,668
1.67%
8,307
10.14%
st70
675
680
0.74%
690
2.22%
712
5.48%
ei176
538
552
2.60%
563
4.64%
583
8.36%
pr76
108,159
111,085
2.71%
11,,250
2.85%
119,692
10.66%
rat99
1,211
1,388
14.62%
1,319
8.91%
1,314
8.51%
kroA 100
21,282
23,751
11.60%
38,200
79.49%
23,356
9.75%
kroB 100
22,141
23,790
7.45%
35,511
60.38%
23,222
4.88%
kroC100
20,749
22,672
9.27%
30,642
47.67%
21,699
4.58%
kroD100
21,294
23,334
9.58%
32,211
51.60%
22,034
3.48%
kroE100
22,068
23,253
5.37%
27.164
23.09%
23,516
6.56%
rd100
7,910
7,944
0.43%
8,152
3.05%
8,944
13.07%
eil 101
629
635
0.95 %
667
6.04%
673
7.00%
lin105
14,379
16,156
12.36%
51,325
256.94%
15,193
5.66%
pr107
44,303
54,378
22.74%
205.519
363.89%
45,905
3.62%
pr124
59,030
59,516
0.82%
167,494
183.74%
65,945
11.71%
bier127
118,282
121,122
2.40%
207,600
75.51%
129,495
9.48%
ch130
6,110
6,175
1.06%
6,316
3.37%
6,498
6.35%
pr136
96,772
98,453
1.74%
102.877
6.36%
105,361
8.88%
pr144
58,537
61,207
4.56%
183,583
213.61%
61,974
5.87%
ch150
6,528
6,597
1.06%
6.877
5.34%
7,210
10.45%
kroA150
26,524
30,078
13.40%
42,335
59.61%
28,658
8.05%
kroB 150
26,130
28,169
7.80%
35,511
60.38%
27,404
4.88%
pr152
73,682
75,301
2.20%
103,110
39.93%
75,396
2.33%
u159
42,080
42,716
1.51%
115,372
174.17%
46,789
11.19%
rat195
2,323
2,955
27.21%
3,661
57.59%
2,609
12.31%
d198
15,780
68,104
331.57%
16,138
2.27%
kroA200
29,368
32,522
10.74%
58,643
99.68%
31,949
8.79%
kroB200
29,437
50,867
72.79%
31,522
7.08%
ls225
126,643
127,731
0.86%
141,628
11.83%
140,626
11.04%
tsp225
3,916
4,354
11.18%
24.816
533.70%
4,280
9.30%
pr226
80,369
91,560
13.92%
101,992
26.90%
84,130
4.68%
gil262
2,378
2,490
4.71%
2,683
13.24%
2,623
10.30%
pr264
49,135
59,109
20.30%
338,506
588.93%
54,462
10.84%
a280
2.579
2,898
12.37%
11,810
357.92%
3,001
16.36%
pr299
48,191
59,422
23.31%
513,673
938.83%
51,903
7.70%
lin318
42,029
45,918
9.25%
reported in previous work.
de O.
Costa et al. 2020),
Kool et al. 2019
3 (Furthest Insertion Heuristic)
23

---

Under review as a conference paper at ICLR 2022
Table 16: Comparison of Performances TSPLIB Part III
Problems
OPT
OR-Tools'
GPN
2-opt
Len.
Gap
Len.
Gap
Len.
Gap
ei151
426
436
2.35%
430
0.94%
446
4.69%
berlin52
7,542
7,945
5.34%
8,820
16.95%
7,788
3.26%
st70
675
683
1.19%
734
8.74%
753
11.56%
ei176
538
561
4.28%
604
12, 27%
591
9.85%
pr76
108,159
111,104
2.72%
124,404
15.02%
115,460
6.75%
ra199
1,211
1,232
1.73%
1,856
53.26%
1.390
14.78%
kroA100
21,282
21,448
0.78%
29,676
39.44%
22,876
7.49%
kroB 100
22.141
23,006
3.91%
31,396
41.80%
23,496
6.12%
kroC100
20,749
21,583
4.02%
29,638
42.84%
23,445
12.99%
kroD100
21,294
21,636
1.61%
31,343
47.19%
23,967
12.55%
kroE100
22,068
22,598
2.40%
33,666
52.56%
22,800
3.32%
rd100
7,910
664
5.56%
772
22.73%
702
11.61%
lin105
14,379
14,824
3.09%
24,271
68.79%
15,536
8.05%
pr107
44,303
46,072
3.99%
80,744
82.25%
47,058
6.22%
pr124
59,030
62,519
5.91%
103,785
75.82%
64,765
9.72%
bier127
118,282
122,733
3.76%
190,187
60.79%
128,103
8.30%
ch130
6,110
6,284
2.85%
8,785
43.78%
6,470
5.89%
pr136
96,772
102,213
5.62%
156,543
61.76%
110,531
14.22%
pr144
58,537
59,286
1.28%
116,692
99.35%
60,321
3.05%
ch150
6,528
6,729
3.08%
9,973
52.77%
7,232
10.78%
kroA150
26,524
27,592
4.03%
47,457
78.92%
29,666
11.85%
kroB150
26,130
27,572
5.52%
43,600
66.86%
29,517
12.96%
pr152
73,682
75,834
2.92%
145,698
97.74%
77.206
4.78%
u159
42,080
45.778
8.79%
87,468
107.86%
47,664
13.27%
rat195
2,323
2.389
2.84%
4,960
113.42%
2,605
12.14%
d198
15,780
15,963
1.16%
37,267
136.17%
16,596
5.17%
kroA200
29,368
29.741
1.27%
61,493
109.93%
32,760
11.55%
kroB200
29,437
30,516
3.67%
64,139
117.89%
33,107
12.47%
ts225
126,643
128,564
1.52%
265,886
109.93%
138,101
9.05%
tsp225
3,916
4,046
3.32%
9,501
142.62%
4,278
9.24%
pr226
80,369
82,968
3.23%
198,299
146.74%
89,262
11.07%
gil262
2.378
2,519
5.93%
4,510
89.66%
2,597
9.21%
pr264
49,135
51,954
5.74%
151,429
208.19%
54,547
11.01%
a280
2,579
2,713
5.20%
6,247
142.23%
2,914
12.99%
pr299
48,191
49,447
2.61%
172,390
257.72%
54,914
13.95%
lin318
42,029
103.643
146.60%
45,263
7.69%
as reported in previous work.
Perron & Furmon), 2
(Ma et al.
2019
24


Reviews:
[{"review_id": "kHT8tvcM1g-", "reviewer": "Reviewer_XHWq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n- The use of equivariance properties in deep learning models for TSP is promising and, to the best of my knowledge, new.\n- The proposed method show competitive results, generalising to TSP instances of different sizes, which is an important and useful trait that is relatively rare in deep learning approaches to combinatorial optimisation.\n- The paper is well written and easy to follow. The experimental details are well explained in the appendix and the authors promised to release their code upon publication, so I see no reproducibility issues.\n\n### Weaknesses\n- The main contribution of the paper seems to be the use equivariance properties in the TSP, while other aspects of the model are mainly effective tweaks of existing ideas. In particular, the idea to interleave reinforcement learning with traditional combinatorial optimisation heuristics is not entirely new. A similar approach has already been explored in [1].\n- Most if not all of the design choices in the paper are very much tailored for the TSP, so I am not confident the approach is *naturally* extendable to other combinatorial optimisation problems as the authors claim. Such an extension would require a whole other set of equivariance properties, local search heuristics, feature engineering tricks and neural architectures, so it is not even clear what aspects of the method the authors deem transferable to other problems.\n\n### Minor issues\n- If I understood it correctly the ablation with respect to the combined local search only considers its influence during training time, and all results include a local search step. It would be interesting to see the gap between the quality of the tour output by the deep learning model and the one refined by local search heuristics.\n- In page 3, it reads \"A state $s_N$ contains the coordinates of the last unvisited city and those of the first and last visited cities\". Should it not be \"unvisited cities\" instead of \"last unvisited city\"?\n\n[1] Cai, Qingpeng, et al. \"Reinforcement learning driven heuristic optimization.\" arXiv preprint arXiv:1906.06639 (2019).", "summary_of_the_paper": "The paper employs equivariance properties and local search heuristics to derive a deep learning model capable of generalising to TSP instances of different sizes. The model constructs a tour, one city at a time, by learning a distribution (policy) over unvisited cities which is optimised via REINFORCE. The solution is further refined with a combination of different local search heuristics, and policy gradients are computed with respect to the final improved solution to smooth the loss landscape. The equivariance in TSP is mostly exploited during preprocessing steps—where rotation, translation and reflection operations are applied to the coordinates of each city—but is preserved by the model architecture which consists of a graph neural network and attention mechanisms. The model is trained with stochastic curriculum learning only on small TSP instances ($\\leq 50$ cities) but is shown to have competitive performance on problems with up to 1000 cities.", "summary_of_the_review": "The paper proposes an effective deep learning model to tackle generalisation in the TSP. While the ideas of the paper are not all novel and somewhat restricted to the TSP, the authors do a great job at integrating previous work on deep learning for combinatorial optimisation into an effective model capable to generalise across problems of different sizes, which is an important challenge in the field. In particular, the use of equivariance properties and the ablation study in the paper should be quite insightful for future work on deep learning for combinatorial optimisation problems.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_jrnN26kGAt", "reviewer": "Reviewer_eA3s", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n1. The paper is clear and well-written \n2. The proposed preprocessing pipeline is well-motivated and extends nicely previous approaches, in particular by reapplying the preprocessing at each step of the solution construction. It could be leveraged by other learning-based method for solving the TSP.\n3. The approach has excellent experimental results:\n    * Performance close to (reps. better than) reported state-of-the-art learning-based methods on synthetic (resp. realistic) TSP instances with up to 1000 nodes\n    * Good generalisation: one model trained with a range of small instance sizes (up to 50 nodes) is able to generalise to unseen and much larger TSP instances (up to 1000).\n    * The ablation study is useful to show the impact of the different components of the approach \n\n\n**Weaknesses** \n1. Missing references to related works, which impacts the novelty claims:\n    * “To the best of our knowledge, no other work uses curriculum learning for designing an RL-based solver for TSP.” See reference [1] below.\n    * The authors claim that (to the best of their knowledge) they are the first to update the encoding of the state to take into account the removal of the visited nodes. This has been explored in (at least in) [2].\n2. The proposed approach is presented as a novel approach that exploits “equivariance” but it seems to me that it mostly exploits the properties of the TSP (indeed invariance of the solution to certain transformations of the coordinates) to preprocess the instances. Then the only equivariance that is exploited by the model is with respect to the node ordering, by using a GNN, which is a pretty standard choice of architecture (see e.g. cited [Joshi et al 2019], [Fu et al 2020]). \n3. Overall, the proposed approach is quite specific to the TSP (the preprocessing, the local search and the architecture), it is not straightforward how much of it could be exploited for solving other CO problems. \n4. Some imprecisions/missing information, see Questions.\n\n[1] Lisicki et al. \"Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimization.\" Workshop on Learning Meets Combinatorial Algorithms @ NeurIPS 2020 \n\n\n[2] Peng et al, A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems. International Symposium on Intelligence Computation and Applications. 2019\n\n**Questions**\n1. The form of the policy gradient in equation (8) could be interpreted as the standard policy gradient with as baseline the value of the solution after applying local search. Since the log probabilities correspond to the model’s output solution and not the improved one by local search. Can you comment if this interpretation is correct or not?\n2. Given the form of the scores in (9), as normal distributions with mean e the index of the current epoch, when (if) e becomes much bigger than 50 during training, the probability of sampling graphs of size 50 or 10 will be quite close, right? Is it intended? What is the number of epochs range?\n3. What is the impact on training time of adding the local search, updating the encodings of all nodes and the preprocessing?\n4. Table 1: The results for GCN* are different (a bit worse) from what is reported in the paper [Joshi et al 2019b]. Why is there a difference and why not use the beam-search version of their method the gives better results for running times similar to the proposed eMAGIC?\n5. In general, what is the motivation behind the chosen baselines? Versus more recent approaches such as [3]? Why are the baselines not the same in Tables 1-2 and 3? Why not include Concorde and LKH results in Table 3?\n6. Table 2: what is the difference between GPN^*5 and GPN^5?\n7. Table 3: \n    * what are the running times? this is key to be able to compare the different methods.\n    * why are the results of Furthest insertion and OR tools not reported for instances with 400-1002 nodes?\n\n\n[3] Kwon et al, POMO: Policy Optimization with Multiple Optima for Reinforcement Learning, NeurIPS 2020\n\n\n\n**Additional feedback**\n\nMinor typos, mathematical inconsistencies and suggestions\n* Introduction:  “equivariance for e” etc —> “e for equivariance” (and same for the others) would be a more standard acronym definition\n* Sec 3: “this RL problem corresponds to a repeated N-horizon sequential decision-making problem.” —> repeated (N-t)-horizon ?\n* Sec 4.1: “and any coordinates x after preprocessing by $\\tilde{x}$” —> missing bold\n* Sec 4.2\n    * Should \\tilde{x}_{\\sigma(t-1)} be replaced by \\tilde{x}_{\\sigma(t)} in the definition of the vector $x$ at $\\sigma(n)$? (As in the definition for $\\sigma(1)$)\n    * The MLP encodes the information about visited cities —>  about the first visited city?\n    * As a GNN, it is invariant with respect to .. —> equivariant \n* Sec 5: It seems the sign of the gradient in equation (8) is inconsistent with what is presented in Appendix B\n* Sec 6\n    * …not being to solve\n    * Tables 1 and 2: \n        * the model from [Kool et al 2019] could be called AM instead of GAT for clarity \n        * Putting the best optimality gap in bold would be helpful \n    * …in the their papers\n\n\n", "summary_of_the_paper": "The paper proposes a series of techniques and a new model to learn to solve the TSP using RL. First, a number of preprocessing steps are presented in order to transform a TSP instance into a standardized form. Then, a new encoder-decoder architecture is proposed, based on GNN, MLP and attention modules. The authors propose a modification of the policy gradient algorithms for training by replacing the value of the policy-generated solution by its value after applying a local search heuristic, and use the original value as a baseline. Finally they use a curriculum learning approach to increase the difficulty of the instances seen during training, the difficulty here being represented by increasing the size of the instances, within a given interval. Experimental results are presented on standard synthetic and realistic TSP instances of size up to 1000 nodes. \n", "summary_of_the_review": "I would vote for reject. My main concern is about the applicability of the proposed contributions beyond the TSP. Clearly the proposed approach is great for the TSP, but it is also somewhat hand-crafted for it (see weaknesses). To me the significance of a TSP-specific learning technique is limited — unless it clearly outperforms specialised TSP solvers such as Concorde or LKH, which is not claimed here. The ultimate goal of learning-based heuristics for combinatorial problems is to replace the handcrafted problem-specific techniques by end-to-end ones. Proving the relevance of the contributions for solving other CO problems would make the paper much stronger.\n\n\n--------\n### Update after rebuttal \n\nI have appreciated the high quality of the authors rebuttal. My concerns and questions were properly addressed, in particular regarding\n* the explanation of the proposed smoothed gradient, \n* the novelty with respect to previous works,\n* and the applicability of the proposed contributions beyond the TSP.\n\nOverall, I think the paper provides a set of well-motivated contributions that lead to an RL-based TSP heuristic with a significant improvement in generalisation performance, compared to current “similar” methods. Some of the proposed techniques could be adapted to other CO problems/ML-based CO heuristics. Therefore I believe this paper can be interesting for the NCO community to participate in addressing the well-recognized problem of generalization of ML-based CO solvers.\n\nI am happy to revise my score from 5 (marginally below acceptance threshold) to 8 (accept good paper).\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Zv7nTMMbbRO", "reviewer": "Reviewer_n7h8", "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": "Originality: Two contributions are original. The first one is algorithmic, i.e., including local search in the training loop of policy gradient. The second is engineering, i.e., applying equivariant preprocessing at each step instead of only once at the beginning. With these two novelties, I think this paper clears the bar for originality.\n\nQuality: Overall this paper is of good quality. I have several questions on the technical details:\n1. Could the authors provide a more rigorous derivation for the smoothed policy gradient formula (Equation 8). I did read section B in the Appendix but it jumped from Equation 17, which is the normal policy gradient, to Equation 8 without much explanation. Specifically, is Equation 8 an unbiased gradient estimator for the objective $J^{+}(\\theta)$?\n\nA second question on the gradient computation is about the baseline, which is the value of the rollout tour from the policy. Does subtracting this baseline still yield an unbiased gradient estimator?\n\n2. For the empirical studies, can the authors comment on how many random seeds are used to obtain the RL results and what are the variances among different random seed runs?\n\n3. I also noticed that the compared methods are different for random TSP instances and TSPLIB instances. Can the authors provide an explanation? \n\nClarity: This paper is well-written and easy to understand. Good job!\n\nSignificance: Since I have some important questions regarding the technical contributions, I will need to see the authors’ response in order to have a more informed evaluation of the significance of the paper. In its current state, I think the significance is not enough because of some (potential) technical issues and empirical baseline choices. \n", "summary_of_the_paper": "This paper proposes a novel combination of policy gradient and local search algorithms for the traveling salesman problems (TSP). The main idea is to apply local search to tours generated by policy rollout and compute policy gradients using the (potentially) improved tour from local search. In addition to the algorithmic contribution, this paper also presents a collection of preprocessing steps to ensure problem instance features are equivalent. Empirical studies are provided on random TSP instances as well as those in TSPLIB. Finally, ablation studies show the importance for each component of the proposed algorithm.", "summary_of_the_review": "My current recommendation for the paper is marginally below the acceptance threshold. I like the novel ideas in the paper and I admire the thoroughness to include lots of baselines in the random TSP instances comparison. However, there are some unclear points in the algorithmic details. And for the more realistic TSPLIB instances, the number of baselines is much smaller. These two points left me some doubts about the correctness and the significance of the paper.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-JoNb5hWKhJ", "reviewer": "Reviewer_13UN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. According to the experiment results, we can see that the proposed algorithm has better generalizability on large-scale TSP and realistic TSP than most learning-based algorithms.\n\n2. Authors propose an equivariant model to handle the symmetry of the combinatorial structures, which has some novelty. \n\n3. Authors provide detailed experiments and evaluations of different methods and problem instances. \n\nWeakness:\n1. Compared with the learning-based algorithm [1] in TSP 200, 500, 1000, the proposed algorithm has longer computational time and larger gaps. Meanwhile, compared with the state-of-art OR solver LKH3, the proposed algorithm seems to only have a very marginal advantage: TSP200 (LKH: 2.0m, eMAGIC(S): 2.4m); TSP500 (LKH: 11m, eMACGIC(S): 9.7m); TSP1000 (LKH3: 38m, eMACGIC(S): 27m). I would encourage the authors to show more evidence to prove that your model has some empirical improvement.\n\n2. In the conclusion section, the authors claim that 'We demonstrated its effectiveness both on random and realistic instances, which shows that our model can reach state-of-the-art performance.' However, based on table 1 and table 2, it looks like both LKH3 and [1] have better performance than the proposed model. I would expect the authors to provide some details about this claim.\n\n[1] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large TSP instances. In AAAI, 2021.", "summary_of_the_paper": "This paper introduces a deep RL approach combined with an equivariant model (to handle Euclidean symmetry) and local search heuristics (to improve a tour) to solve traveling salesman problems (TSP), in particular focusing on the generalizability of large-scale instances. The model consists of a graph neural network (GNN), a multi-layer perceptron (MLP), and an attention mechanism. In the training part, this model involves smoothed policy gradient, and stochastic curriculum learning to speed up the training and make the policy more generalizable. The experiments results show that the proposed approach significantly outperforms most learning-based solvers on large-scale randomly generated TSP and realistic TSP.", "summary_of_the_review": "Technically, the proposed model uses a standard RL framework with GNN and attention as encoder and decoder. The authors introduce an equivariant model to capture the combinatorial structures of the TSP, which has some novelty and improves the overall performance, but the ablation study does not show that this model provides very significant added value. \n\nEmpirically, the proposed model can outperform most learning-based algorithms on large-size TSP but still can not beat the state-of-the-art learning-based algorithm [1] both in computational time and objective values. Meanwhile, compared with the state-of-art OR solver LKH3, the proposed algorithm does not have enough advantage in terms of computational time.\n\nTherefore, my decision is weak reject. \n\n[1] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large TSP instances. In AAAI, 2021.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper discusses new RL algorithms for solving large. TSP instances. The algorithm is novel and the problem is important however certain technical questions regarding the soundness of the algorithm were raised. Furthermore, it seems that despite much larger computational time, the algorithm provides only very moderate gains over previous baselines. Finally, it is not clear how the proposed methods (e.g. equivariance) can be applied outside of the TSP problem scope. Thus the concern is the limited impact of the method on the field.

The authors addressed some of the concerns of the reviewers in the rebuttal however it is still not clear:

(1) how the presented mechanism can be applied for other combinatorial problems beyond TSP and therefore how useful it can be for the machine learning community,

(2) how novel the paper is (the use of equivariance is as direct as in the regular graph neural network setup).

Furthermore, the experiments show that the deep learning approach to TSP is still not competitive with standard non-machine baselines. Thus it is not clear whether the proposed algorithm is a right approach to solve this problem, even though it beats other deep learning techniques. The paper is very well written though and the presented method is definitely of value to the research community working on the TSP. Therefore it seems that at this point the paper is more suited for one of the mathematical journals on combinatorics and graph theory.
Decision: Reject