Graph Neural Network Guided Local Search for the Traveling Salesperson Problem
Authors: Benjamin Hudson
Qingbiao Li
Matthew Malencia
Amanda Prorok
Venue: ICLR 2022 Poster (2022)
Keywords: Traveling Salesman Problem
Graph Neural Network
Metaheuristic
Guided Local Search
Hybrid

Abstract: Solutions to the Traveling Salesperson Problem (TSP) have practical applications to processes in transportation, logistics, and automation, yet must be computed with minimal delay to satisfy the real-time nature of the underlying tasks. However, solving large TSP instances quickly without sacrificing solution quality remains challenging for current approximate algorithms. To close this gap, we present a hybrid data-driven approach for solving the TSP based on Graph Neural Networks (GNNs) and Guided Local Search (GLS). Our model predicts the regret of including each edge of the problem graph in the solution; GLS uses these predictions in conjunction with the original problem graph to find solutions. Our experiments demonstrate that this approach converges to optimal solutions at a faster rate than three recent learning based approaches for the TSP. Notably, we reduce the mean optimality gap on the 100-node problem set from 1.534% to 0.705%, a 2x improvement. When generalizing from 20-node instances to the 100-node problem set, we reduce the optimality gap from 18.845% to 2.622%, a 7x improvement.

Published as a conference paper at ICLR 2022
GRAPH NEURAL NETWORK GUIDED LOCAL SEARCH FOR THE TRAVELING SALESPERSON PROBLEM
Benjamin Hudson
Qingbiao Li Department of Computer Science and Technology University of Cambridge q12950 cam ac uk
Department of Computer Science and Technology University of Cambridge bh5110cam ac.
Matthew Malencia
Amanda Prorok
Department of Electrical and Systems Engineering University of Pennsylvania ma malencias aeseas. upenn.edu
Department of Computer Science and Technology University of Cambridge asp450 50 cam. ac. uk
ABSTRACT
Solutions to the Traveling Salesperson Problem (TSP) have practical applications to processes in transportation, logistics, and automation, yet must be computed with minimal delay satisfy the real-time nature of the underlying tasks. How- ever, solving large TSP instances quickly without sacrificing solution quality re- mains challenging for current approximate algorithms. To close this gap, we present a hybrid data-driven approach for solving the TSP based on Graph Neu- ral Networks (GNNs) and Guided Local Search (GLS). Our model predicts the regret of including each edge of the problem graph in the solution; GLS uses these predictions in conjunction with the original problem graph find solutions. Our experiments demonstrate that this approach converges to optimal solutions at a faster rate than three recent learning based approaches for the TSP. Notably, we reduce the mean optimality gap on the 100-node problem set from 1.534% 0.705%. a 2x improvement. When generalizing from 20-node instances to the 1o0-node problem set, we reduce the optimality gap from 18.845% 2.622%, 7x improvement.
INTRODUCTION
Sixty years ago, the route of a delivery truck would have been fixed well before the truck departed the warehouse. Today, thanks the availability of real-time traffic information, and the option to transmit instructions to the driver to add or remove delivery locations on-the-fly, the route is no longer fixed. Nevertheless, minimizing the length duration of the route remains important problem. This is an instance of the Traveling Salesperson Problem (TSP), and one of a growing number of practical applications which require solving combinatorial optimization problems in real time. In these problems, there is often a cost attributed to waiting for an optimal solution or hard deadlines at which decisions must be taken. For example, the driver cannot wait for new solution to be computed they may miss their deliveries, or the traffic conditions may change again. There is need for general, anytime combinatorial optimization algorithms that produce high-quality solutions under restricted computation time. This remains challenging for current approaches, they specialized for a specific problem (with specific assumptions and constraints), or fail to produce good solutions quickly.
Contributions We present a hybrid data-driven approach for approximately solving the Euclidean TSP based on Graph Neural Networks (GNNs) and Guided Local Search (GLS), which we demon- strate converges to optimal solutions more quickly than three recent learning based approaches. We provide the following contributions:
Our GLS algorithm is guided by the global regret of each edge in the problem graph. This allows the algorithm to differentiate edges that are very costly include in the solution from ones that are not so costly, whether or not they are part of the optimal solution. Thus, using regret allows us find high-quality, rather than optimal, solutions very quickly. We are the first

---

Published as a conference paper at ICLR 2022
use measure of global regret, which we define the cost of enforcing decision relative to the cost of an optimal solution.
We make this computationally tractable by approximating regret with learned representation.
Our GNN-based model operates the line graph of the problem graph, which allows to build a network without node features, focusing only on edge weight.
We present experimental results for our approach and several learning based approaches that are aligned with recent guidelines for computational testing of learning based approaches for the TSP. Our experiments emphasize the trade-off between solution quality and time.
We reduce the mean optimality gap on the 50-node problem set from 0.268% to 0.009%, x0x times improvement, and on the 100-node problem set from 1.534% 0.705%, a 2X improve- ment. When generalizing from 20-node instances to the 100-node problem set, we reduce the mean optimality gap from 18.845 18.845% to 2.622%, 7x improvement.
2 RELATED WORK
The Operations Research (OR) community is responsible for the majority of research in algorithms for solving combinatorial optimization problems. Concorde (Applegate et al.) 2006) is widely garded as the best exact TSP solver. As an exact solver, it can guarantee the level of optimality of the solutions it finds. It uses cutting plane algorithms (Dantzig et al. 1954 Padberg & Rinaldi 1990 Applegate et al., 2003) and branch-and-cut methods to iteratively prune away parts of search space that will not contain an optimal solution. LKH-3 (Helsgaun 2017). and its predecessor, LKH- 2 (Helsgaun 2009), are approximate TSP and Capacitated Vehicle Routing Problem (CVRP) solvers based on the K-opt heuristic (Lin & Kernighan| [973). While these solvers do not provide any guar- antees, experimentation has demonstrated that they extremely effective. Concorde, LKH-2 and LKH-3 are highly specialized and efficient solvers which can solve challenging TSPs in seconds.
However, practical real-time routing problems often impose constraints top of the basic TSP or CVRP problem defimitions. Highly-specialized solvers are difficult to adapt these new constraints. Thus, there is need for general algorithmic frameworks that can produce high-qualit, solutions with minimal computation time. To address this, Arnold & Sörensen 2019a) introduce KGL.S, GLS algorithm for the CVRP that is guided by three engineered features. They demonstrate that their algorithm find solutions almost good as those found by state-of off-th--atttttttt metaheuristics in a fraction of the time. Our work also aims to address this gap.
Machine learning offers way to construct flexible, yet effective combinatorial optimization algo- rithms. This area of research has existed for more than three decades (Smith) 1999). yet new neural architectures, especially GNNs, have driven a surge of activity in this area. As noted by Bengio et al. (2021); Cappart et al. (022I), classical combinatorial optimization approaches solve each problem instance in Isolation, overlooking the fact that in practice, problems and their solutions stem from related data distributions. Machine learning offers way to exploit this observation. We classify learning based approaches for solving the TSP into the three categories identified by Bengio et al. (2021;; ; our approach belongs to the second category, described below.
ML alone provides solution. These approaches use a machine learning model to output solutions directly from the problem definition. VVinyals et al. (2015) propose PtrNet, a sequence-to-sequent
model based LSTMs, which iteratively constructs solution by outputting the permutation of the input nodes. They train their model using expert solutions from Concorde. They use beam search (Reddyl 1977) to produce better solutions than those sampled from their model directly. Bello al. (016)) present a method of training PtrNet without supervision using policy gradients. Their "active search" method resembles early neural network- based approaches to combinatorial optimization, in which a model was trained online to solve a particular problem instance (Smith) 1999). This method effectively solves each problem in isolation, thus it does not leverage expertise extracted from distribution of training problem instances. Kool al. (2018) take similar approach to Bello et al. (2016) but use a Transformer architecture (Vaswani et al. (011)) rather than an LSTM. Their model can also be seen as Graph Attention Network (GAT) Veličković et al.) (017) applied to a complete graph. Kwon et al. (2021) also take a similar approach but leverage the symmetry of many combinatorial optimization problems to improve performance.
Joshi et al. (2019) train model produce a heatmap of which edges in the TSP graph are likely to be part of the optimal solution, and reconstruct valid tours using beam search. Similar to Vinyals
et al. 2015), they train their model using expert solutions from Concorde. Kool et al. (202) extend
2

---

Published as a conference paper at ICLR 2022
the work of Joshi et al. (2019) to VRPs, and use dynamic programming method construct tours. Also in this category, Fu et al. (202I) train a model to output a heatmap for small TSP instances to and sample small sub-graphs from large instances to construct heatmaps for large instances. They train their approach using reinforcement learning, and use Monte Carlo tree search (MCTS) con- struct valid tours.
ML provides information to an OR algorithm. Machine learning may not be suitable solve a combinatorial optimization problem alone. Instead, it can provide information to augment a com- binatorial optimization algorithm. Deudon et al.] (2018) use a model based the Transformer architecture to construct solutions iteratively and train it using policy gradients (they take a similar approach to Kool et al. 2018). They apply 2-opt local search heuristic to solutions sampled from their model. In contrast prior work, we are the first to use a machine learning model to approx- imate regret. Furthermore, many previous works that produce predictions on edges (Joshi et al.) 2019 Kool et al. 2021] Fu et al. 2021) construct tours using heuristics, whereas our knowledge, we are the first to use predictions to inform a metaheuristic (GLS).
ML makes decisions within an OR algorithm. Finally, machine learning model can be embed- ded inside a combinatorial optimisation algorithm. this paradigm, a master algorithm controls the high-level procedure while repeatedly calling a machine learning model to make lower level deci- sions. Dai al. (2017) present a model that uses a GNN to learn an embedding of the current partial solution and a DQN (Mnih et al. 2015) to iteratively select nodes to insert using a cheapest inser- tion heuristic. They also use an "active search" method when solving the TSP. Wu al. (2020) and da Costa et al. (2020) present policy gradient algorithms to learn policies to apply 2-opt operations to existing feasible solutions. [w et al. (2020) use a Transformer architecture. da Costa et al. (2020) use combination of GCN and RNN modules, and acheive better results. These approaches can either be seen as end-to-end learning approaches belonging to the first category, or as local search procedures where ML model decides where to apply an operator.
PRELIMINARIES
Traveling Salesperson Problem We focus on the Euclidean TSP, although our approach can be applied to other routing problems, such as the CVRP. A problem with n cities, typically denoted TSPn, is represented as complete, undirected, weighted graph G = E) with n nodes. The edges E represent connections between cities and are weighted by the Euclidean distance between the adjacent nodes. A solution, tour, is Hamiltonian cycle: a closed path through the graph that visits every node exactly once. An optimal solution is a cycle of minimum weight.
Regret Regret measures the future cost of an action that also yields an immediate reward, and is typically used to make greedy combinatorial optimization algorithms less myopic. Generally, regret is computed over a fixed horizon. For example, Potvin & Rousseau (1993) evaluate the cost of inserting a node in the best versus second-best position when constructing a CVRP solution. HHassin & Keinan (2008) solve the TSP using regret, allowing a greedy construction heuristic to remove the most recently inserted node. It is not computationally feasible calculate regret over global horizon, for example, for all possible insertion sequences. However, if it were possible, a greedy algorithm could compute an optimal solution by selecting the lowest regret decision at each step.
general improvement heuristic. Starting from an initial solution, local search iteratively moves to neighboring solutions that are lower cost than the cur- rent solution according the objective function g(s). Neighboring solutions are solutions that are reachable from given solution by applying a certain function, or operator. The set of all solutions reachable from another solution by applying an operator define the neighborhood of that operator. The algorithm terminates when all neighboring solutions are inferior to the current solution, meaning the search has reached a local optimum.
Local Search Local Search (LS)
Guided Local Search Guided Local Search (GLS) is a metaheuristic that sits on top of LS and allows it to escape local optima (Voudouris & Tsang 1996). To apply GLS, the designer must define some aspects of a solution. When trapped local optimum, the algorithm penalizes certain aspects of the current solution which are considered to be unfavorable. The underlying LS procedure searches using objective function that is augmented by these penalties, thus it is incentivized to
3

---

Published as a conference paper at ICLR 2022
remove heavily penalized aspects from the solution. The augmented objective function h(s) is
h(s) g(5) prl((s),
where is solution, g(s) ) is the objective function, À is scaling parameter, indexes the aspects, M is the number of aspects, p; is the current number of penalties assigned to aspect i, and I; is an indication of whether exhibits aspect i, i.e.
{
if exhibits aspect
(s))
otherwise.
For the TSP, aspects of the solution are often defined as the edges in the problem graph. Therefore, (s) indicates an edge in the solution 8. Upon reaching local optimum, which aspects are penalized is determined by utility function. The utility of penalising aspect i, util; is defined as G;
us.), = I((sa) 1+
(3)
where s, is the solution at a local optimum, (s.) indicates if the solution exhibits aspect and oa is the cost of the aspect i. The cost of an aspect measures how unfavorable it is. The higher the cost, the greater the utility of penalizing that aspect. In the context of the TSP, the cost can be the weight of the edge (Voudouris & Tsang, 1999), or a combination of various features (Arnold Sörensen, 2019a). Conversely, the more penalties assigned to that aspect, the lower the utility of penalising again. The aspects with the maximum utility are always penalized, which means increasing pi by one. This penalization mechanism distributes the search effort in the search space, favoring areas where a promise shown (Voudouris & Tsang, 1996).
We use a variation of the classical GLS algorithm (see Voudouris T'ang 1999) that applies al- ternating optimisation and perturbation phases (see Arnold & Sörensen (2019)). During opti- mization phase, the local search procedure guided by the original objective function g. During a perturbation phase, it is guided by the augmented objection function h. After an edge is penalized, the local search is applied only on the penalized edge. That is, only operations that would remove the penalized edge are considered. This differs from the local search during the optimization phase, which considers all solutions in the neighborhood of the given operator. The perturbation phase continues until K operations (operations that improve the solution according to the augmented ob- jective function h) have been applied to the current solution. These operations perturb the solution enough for the local search to escape a local minimum. The alternating phases continue until the stopping condition is met.
4
METHOD
Our hybrid method, shown in Figure combines machine learning model and metaheuristic. Our GNN-based model learns an approximation of the global regret of including each edge of the problem graph in the solution. The metaheuristic, GLS, uses this learned regret conjunction with the original problem graph to quickly find high-quality solutions. The learned regret allows the algorithm to differentiate between edges which are costly to include in the solution and ones that not so costly, thus improving its ability to steer the underlying local search procedure out of local minima and towards promising areas of the solution space.
Line Graph Transtoraation (a)
Regret Prediction Model
Guided Local Search (c)
TSP Graph
Predicted Regret
Solution
Figure I: From a TSP formulated as graph, we take the line graph (a) and input it into our regret approximation model (b), which predicts the regret of including each edge in the solution. GLS (c) uses these predictions in conjunction with the original problem graph to quickly find a high-quality solution.
4

---

Published as a conference paper at ICLR 2022
4.1 GLOBAL REGRET
We define global regret as the cost of requiring a certain decision to be part of the solution relative to the cost of globally optimal solution. Unlike previous heuristics using regret, which calculate the cost of a decision relative to some fixed number alternatives (for example, the next best, or two next best options), our regret is measured relative to global optimal solution. Decisions that are part of an optimal solution have zero regret, and all other decisions have positive regret. Mathematically,
g(5
F g(s*)
1,
(4)
where r; is the regret of decision i, y is the objective function, 8; is optimal solution with i fixed, and s* globally optimal solution. With perfect information, greedy algorithm could construct an optimal solution by sequentially selecting the lowest-regret decisions.
In the TSP, decisions correspond to which edges are included in the solution, thus regret is defined as the cost of requiring that a certain edge be part of the solution. We posit that using regret is preferable directly classifying which edges are part of the optimal solution (which is the approach taken by Joshi et al.) 2019). Where classification can produce probability that the edge is part of optimal solution, regret can differentiate between edges that are very costly have as part of the solution and ones that are not so costly, whether or not they are part of the optimal solution. Thus, using regret furthers our goal of finding high-quality, rather than optimal, solutions with minimal computation time.
4.2 REGRET APPROXIMATION MODEL
Calculating the global regret of edge in the TSP graph requires solving the TSP itself, which is computationally intractable. Instead, we aim learn a function ny that approximates the regret of an edge ray. We use GNNs to achieve this, as they are universal function approximators that operate on graph-structured data.
Input transformation Typically, GNNs aggregate messages and store states on the nodes of a graph (Gilmer et al., (017). Instead, input the line graph of the original problem graph into
model. The line graph L(G) of an undirected graph is graph such that there exists a node in L(G) for every edge in G, and that for every two edges in G that share node, there exists an edge between their corresponding nodes LG)). Figure 2 illlsttate this transformation for simple graph. The result is that our model aggregates messages and stores states on the edges of the problem graph (the nodes of the line graph). Primarily, this allows to build models with no node features, which is advantageous as the edge weights, not the specific node locations, are relevant when solving the TSP. For complete, undirected graph G' with nodes, there n(n 1)/2 nodes and r2(n 1)(n 2) edges in LG)). Thus, although G is complete, LGG) can be very sparse.
(a) G
(b) L(G)
Figure 2: An example of a graph and the corresponding line graph. The edges in G are the nodes in LGG), and vice-versa.
Model architecture Our model consists of an embedding layer, several GNN layers, and an output layer. The embedding layer edge-wis wise fully connected layer that computes d, dimdennnsi edge embeddings from di-dimensionaa edge features. Node features, if used, are concatenated onto the feature set of the adjacent edges. The forward pass of the embedding layer is written as
(5) where h2 is the initial embedding of edge ij, W is learnable weight matrix, X, are the input features of edge ij (including any node features), and is a set of learnable biases. We use d, and d, 128 28. The edge embeddings are updated using T message passing layers. Inspired by the
hi = Wxxy + b,
5

---

Published as a conference paper at ICLR 2022
encoder layer of Kool et al. (0118), each layer consists of multiple sublayers. The forward pass is given by
h ( + MMA LG))),
(6)
h SEN (bg + fiz (h: 1))
where ÍMHA is a multi-headed GAT layer (Velicković et al. 2017). fFF is a feedforward layer, fBN is batch normalisation (loffe & Szegedy 2015). and h is hidden state. The layers do not share parameters. The GAT layer uses M 8 heads and dimensionality da = 16, and the FF layer uses one hidden sublayer with dimensionality 512 and ReLU activation. Finally, the output layer is single edge-we adge-wise fully connected layer that computes one-dimensional output from the di-dimensional node embeddings computed by the final message passing layer. This is written as
fig = Wh + b,
(8)
where P.y is the output for edge ij and hi is the final embedding of that edge.
4.3 REGRET-GUIDED LOCAL SEARCH
We adapt GLS to use regret to solve the TSP, including how the initial solution built, the local search procedure, and the perturbation strategy. Our GLS uses alternating optimization and pertur- bation phases. During an optimization phase, the local search procedure greedily accepts changes to the solution until it reaches a local minimum. During a perturbation phase, the algorithm penalizes and attempts remove edges in the current solution with high regret, thus allowing it to escape local minima while simultaneously guiding it towards promising areas of the solution space, i.c., those with low regret. Effectively, the regret predictions produced by our model allow our GLS algorithm to undo costly decisions made during the greedy optimization phase.
Initial solution We use greedy nearest neighbor algorithm to construct an initial solution. Begin- ning from the origin node we iteratively select the lowest-regret edge leading an unvisited node, until all nodes have been visited.
Local Search neighborhoods Our LS procedure uses two solution operators for the TSP, relocate and 2-opt. alternates between using either operator, and uses a "best improvement" strategy, meaning that it exhaustively searches the neighborhood corresponding with the current operator and accepts the solution that improves the objective function the most before continuing with the other operator. The algorithm terminates when no improvement can be found in either neighborhood. The relocate operator simply changes the position of single node in the tour. The 2-opt operator selects two nodes in the tour to swap. This divides the tour into three segments: an initial segment, an intermediate segment, and a final segment. The tour is reassembled beginning with the initial segment, the intermediate segment in reverse order, and the final segment. It is a special case of the K-opt operator (Lin & Kernighan| 1973), although it was introduced earlier (Croes 1958).
Perturbation strategy We define the cost of an edge as the predicted regret fi of that edge. The utility of penalizing edge ij, utilij. is therefore defined as
(s.) (sy PgJ
I+P
where we remind the reader that s. is the solution at local optimum, I,y (s.) indicates if the solution contains edge ij, and Pıj is the number of penalties assigned to that edge. The edges of maximum utility are penalized. Afterward, the local search is applied only on the penalized edge. That is, only operations that would remove the penalized edge are considered.
EXPERIMENTS
We train our model using supervised learning. It uses single input feature, edge weight (i.e. the Euclidean distance between adjacent nodes), to predict the regret of the edges in the problem graph. Further details of our implementation are found in Appendix A While further input features could be considered, they come computational cost, as seen Table 4 In Appendix D we compare 11 input features, and demonstrate that edge weight is the most important feature when predicting the regret of edge.

---

Published as a conference paper at ICLR 2022
Evaluation We evaluate the trade-off between solution quality and computation time when solving randomly generated TSPs as well as TSPLIB instance:" Where available, we use publicly available implementations and pre-trained models. There is no publicly available implementation of Arnold & Sörensen (2019a), so we use the GLS implementation described in section 4.3 with the guides described in their paper.
We compare our approach to the following methods, the first six of which are non-learning based, and the other three are learning based:
1. Nearest Neighbour
2. Farthest Insertion
3. Local Search (as described in section 4.3
4. Concorde (Applegate et al. 2006)
5. LKH-3 (Helsgaun (017)
Knowledge-guided local search for the vehicle routing problem (Arnold & Sörensen 2019a
7. Attention, learn to solve routing problems! (Kool et al. 2018)
8. An efficient graph convolutional network technique for the travelling salesman problem Joshi
al. 2019)
9.
Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning (da Costa et al., 2020)
Following Guidelines for the computational testing of machine learning approaches to vehicle rout- ing problems (Accorsi et al. 2021), we conduct two types of experiments. 1) we leave both compu- tation time and solution quality unfixed. We measure the mean optimality gap and computation time per instance across the entire problem set. We use implementations as-described. 2) we fix com- putation time and measure the solution quality, in terms of mean optimality gap and the number of instances solved optimally. This allows for a direct comparison of approaches that was impossible in the first experiments and previous works. Where possible, we modified implementations to run continuously until the computation time limit is reached. We allow up to 10 seconds to solve each problem, including the time required to calculate input features, evaluate a model, to construct an initial solution.
We evaluate the problem sets one instance at time, which allows to accurately measure compu- tation time per instance. We allow parallelism in the GPU sample multiple solutions to a single problem at once, where implementations are configured to do so. We use a common, single CPU and single GPU setup for all experiments. More details the experimental setup and the hyperpa- rameters of different approaches are given in Appendix A
We conduct both types of experiments on three problem sets, TSP20, TSP50, and TSP100, consist- ing of one thousand 20, 50, and 100-node 2D Euclidean TSP instances, respectively. We generate the instances by uniform uniform-randomly sampling node locations in the unit square [0. 1 which is in line with the methods used by Kool et al. (2018); Joshi et al. (019); ; da Costa et al. (2020). In the second type of experiment (fixed computation time), we focus on the learning based approaches and benchmark. Furthermore, learning based approaches from smaller to larger problem sets, and from the randomly generated instances to TSPLIB instances, which are meant to represent real-world problems.
keep Concorde
evaluate the generalization performance of the
The performance of each approach when computation time and solution quality are un- fixed is shown in Table [] Approaches that are not dominated by others (i.e. they produce higher- quality solutions or are faster) are bolded. These values form Pareto front for the trade-off between solution quality and computation time. Non-learning and learning approaches are considered sep- arately. Our approach always lies the Pareto front. These results are visualized in Figure 3 in Appendix B. The results presented for Joshi et al. (2019) differ from the results presented by the authors, due to an implementation error we found in their code (see Appendix A for the correction).
Results
To better evaluate this trade-off, the second experiment fixes computation time and measures the solution quality as it evolves over time. Figure 4 in Appendix B.2 visualizes the performance as function of time, which provides rich understanding of the trade-off made by each approach. Table 2 shows the performance of the learning based approaches after 10 seconds of computation time per instance. Our approach finds better solutions on average than the other approaches for all problem sets, Notably, we reduce the mean optimality gap on the 50-node problem set from 0.268%
Downloaded from http: /ttp:://coooot.p/// 1 .ui.-uiiii -hei httpbe/gg...//ttteeee//........
7

---

Published as a conference paper at ICLR 2022
Problem
Method
Computation time (s)
Optimality gap (%)
Nearest Neighbor Farthest Insertion
0.000=0.000
17.448=10.200 209
0.005=0.000
2.242+2.536
Local Search
0.007=0.003
1.824+3.254
Arnold et al. Concorde LKH-3
10.009#0 0008
0.000=0.00 0000
0. 0.119=0.000 083
0.000=0.00 00000000000
TSP20
0.020=0.019
0.000=0.000
Kool et
0.038
0.069=00255
Joshi et al. O. da Costa et al.
1 1.344 106
2.031+2.5 928
21.120=#0353
0.001=0.022
Ours
10.010=0.008
0.000=0.000
Kwon al."
0.00
Fu et al."
0.000
Nearest Neighbor
0.002+0.000
23.230+7.968
Farthest Insertion
0.065+0.001
7.26343.072
Local Search
0.101
3.357+2.600 603
Arnold et al. Concorde
10.035#0.003
0.040=0. 180
0.258+0.197
0.000=0.0000
TSP50
LKH-3
0.069#0.030
0.000=0.012
Kool et al.
0.124=0.000
0.494+0.655
Joshi al.
3.080=0.18 182
0.884+1 1144+1.700 .7700
O. da Costa et al.
24. 24.338#0.525
0. 136=0.3314
Ours
10.037=0.039
0.009=0.069
Kwon et al." Fu et al."
0.03
0.0145
Nearest Neighbor
0.010=0.000
25.104+6.909
Farthest Insertion Local Search
0.444=0.010
12.456#2.944
0.727=0. 165
4.169+2.00 0.47
Arnold et al. Concorde LKH-3
10.128#0..11 194
1.757+1 .240
0.573+0.771
0.000=0.000
TSP100
0.118+0.022
0.011#0.058
Kool et al.
0.35620.007
2.368=1.185
Joshi et al. O. da Costa et al.
6. 1.127=0.08
1.880#4.097
30.656#0.773
0.773+0.771
Ours
10.108:0.175
0.698+0.801
Kwon al." Fu et al."
0.14
0.037
Table 1: Solution quality and computation time for various approaches. Means and standard de- viations are reported, calculated across the entire problem set. Pareto optimal values (i.c. faster or better solutions) are bolded. Some results (*) are taken directly from papers that do not report computation time per instance, and thus cannot compared.
to 0.009%, a 30x times improvement, and on the 100-node problem set from 1.534% to 0.705%, 2x improvement. Joshi al. (2019) finds more optimal solutions to the TSP100 problem set, but has worse average performance than our approach. Our approach finds more optimal solutions to the TSP20 and TSP50 problem sets than the other approaches.
We evaluate the performance our approach and other learning based approaches when gener- alizing from smaller instances to larger ones, and from randomly generated instances to TSPLIB instances, which are meant represent real-world instances. These results are summarized in Ap- pendix C.I and Appendix C.2 respectively. Our approach generalizes well. Notably, when general- izing from 20-node instances to the 100-node problem set, reduce the mean optimality gap from 18.845% to 2.622%, a 7x improvement.
DISCUSSION
Our approach generalizes to larger problems and to real-world problems well, which may be due to the unique input transformation we apply to the problem graph. We input the line graph L(G) of the problem graph G, which allows the model to aggregate messages and store states edges
8

---

Published as a conference paper at ICLR 2022
Problem
Method
Optimality gap (%)
Optimal solutions (%)
Concorde
0.000=0.000
100.0000
TSP20
Kool et al.
0.069#0.255
84,6000
Joshi et al.
1.000+12.499
97.4000
O. da Costa et al.
0.002+0.027
99.0000
Ours
0.000=0.000
100,0000
Concorde
0.000#0.000
100.0000
TSP50
Kool et al.
0.494+0.655
29.5000
Joshi et al.
1.206+18.066
86.3000
O. da Costa et al. Ours
0.268:00.44 442
48.7000
0.009#0.069
96.2000
Concorde
0.000#0.000
100.0000
TSP100
Kool et al.
1.958 .064
0.3000
Joshi et al. O. da Costa et al. Ours
1.559+4.007
51.6000
1.534=1. 1.098
1,4000
0.705=0.807
20.5000
Table 2:
Solution quality measured after after 10 seconds of computation time per instance. The mean optimality gap and standard deviation, as well as the percentage of optimally solved problems reported. Our approach converges to better solutions at faster rate than the other approaches.
rather than nodes. This allows us to build models without node features, which is advantageous as the edge weights, not the specific node positions, are relevant when solving the TSP. Including the node positions as features, as done by Kool et al.] (2018): Joshi et al.] (2019): da Costa et al. (2020) may hinder the learned policy's ' ability to generalize. Deudon al. (2088) apply PCA the node positions before inputting them into their model so they are rotation invariant, yet they do not report generalization performance. For Euclidean TSP problem graph with nodes, L(G) has n(n - 1)/2 nodes, meaning that although G is complete, L(G) can be very sparse, which may help learning (Cappart et al. (021). However, the model consumes more GPU memory than models using the problem graph G.
Many approaches that learn construction heuristics (for example Kool et al. 2018) treat the tour as permutation of the input nodes. By considering the solution as sequence, these approaches miss out on its symmetry: a TSP solution invariant to the origin city. Outputting the correct sequence becomes increasingly difficult as the number of cities increases. This has recently been addressed by Kwon et al.) (2021), who leverage the symmetry of the TSP in their approach. Our model learns the regret of including a given edge in the solution based on its features and those of its neighbors, which implicitly assumes the symmetry of TSP solution.
We argue that our hybrid architecture is more general than others, as our global regret is defined for most routing problems. When applying our method to new routing problem, the designer need only plug-and-play a local search procedure that is appropriate for the problem. In contrast, methods which learn heuristics cannot always be transferred to other problems. For example, 2-opt cannot be used on routing problems that include pickup and drop-off constraints (Pacheco et al, 2021). A drawback of our approach is that it relies on supervised learning. In future work, our regret approximation model could be trained end-to-end.
CONCLUSION
We present a hybrid data-driven approach for solving the TSP based on Graph Neural Networks (GNNs) and Guided Local Search (GLS). To inform GLS, fast, generalizable approximations of the global regret of each edge. Our model operates on the line graph of the TSP graph, which allows us to build network that uses edge weight the only input feature. This approach allows our algorithm to escape local minima and find high-quality solutions with minimal computation time. Finally, we present experimental results for our approach and several recent learning based approaches that emphasize the trade-off between solution quality and computation time. We demonstrate that our approach converges to optimal solutions at a faster rate than the evaluated learning based approaches.
GNN-based model to compute

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
We gratefully acknowledge the support of the European Research Council (ERC) Project 949940 (gAla).
REFERENCES
Luca Accorsi, Andrea Lodi, and Daniele Vigo. learning approaches to vehicle routing problems, 2021.
Guidelines for the computational testing of machine
David Applegate, Robert Bixby, Vašek Chvátal, and William Cook. Implementing the Dantzig- Fulkerson-Johnson algorithm for large traveling salesman problems. Mathematical Programming, 97(1):91-153, 2003.
David Applegate, Robert Bixby, Vašck Chvatál, and William Cook. The Traveling Salesman Prob- lem: A Computational Study. Princeton University Press, Princeton, NJ, 2006.
Florian Arnold and Kenneth Sörensen. Knowledge-guided local search for the vehicle routing prob- lem. Computers & Operations Research, 105:32-46, 20
Florian Arnold and Kenneth Sörensen. What makes a VRP solution good? The generation of problem-specifii knowledge for heuristics. Computers & Operations Research, 106:280-288, 2019b.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning, arXiv preprint arXiv: 1611:99911 2016.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: A methodological tour d' d'horizon. European Journal of Operational Research, 290(2): 405-421, 2021.
Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. arXiv preprint arXiv:2102.09544, 2021.
G. A. Croes. method for solving traveling-saleee salesman problems. Operations Research, 6(6):791- 812, 1958.
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. arXiv preprint arXiv:2004.01600. 2020.
Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. In International Conference on Neural Information Processing Systems, pp. 6351-6361. 2017.
G. Dantzig, R. Fulkerson, and S. Johnson. Solution of a large-scale Journal of the Operations Research Society of America, 2(4):393-410, 1954.
salesman problem.
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the TSP by policy gradient. In Integration of Constraint Pro- gramming, Artificial Intelligence, and Operations Research, pp. 170-18111111111111 1001 2018.
Zhang-Huu Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model arbitrarily large tsp instances, 2021.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pp- 1263-1272. PMLR. 2017.
Loie Le Gratiet, Stefano Marelli, and Bruno Sudret. Metamodel-bane Sensitivity Analysis: Poly- nomial Chaos Expansions and Gaussian Processes, pp. 1-37. Springer International Publishing, Cham, 2016.
10

---

Published as a conference paper at ICLR 2022
Refael Hassin and Ariel Keinan. Greedy heuristics with regret, with application to the cheapest insertion algorithm for the TSP. Operations Research Letters, 36(2):243-246, 2008.
Keld Helsgaun. General k-opt submoves for the Lin-Kernighan TSP heuristic, Mathematical Pro- gramming Computation, 1(2):119-163, 2009.
Keld Helsgaun. An extension of the salesman and vehicle routing problems. Technical report, Roskilde University, 2017.
TSP solver for constrained traveling
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 448-456. PMLR, 2015.
Chaitanya Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv: arXiv: (eee:09006.7277 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 41266980, 2014.
Wouter Kool, Herke Van Hoof, and Max Welling, Attention, learn to solve routing problems! arXiv preprint arXiv: 183.008803 2018
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic pro- gramming for vehicle routing problems, 2021.
Ycong-Das Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning, 2021.
S. Lin and B. W. Kernighan. An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2):498-516 1973.
M. D. McKay, R. J. Beckman, and Conover. comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics, (2) 239-245, 1979.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, (508):529-55) 533, 2015.
Toni Pacheco, Rafael Martinelli, Anand Subramanian, Túlio A. M. Toffolo, and Thibaut Vidal. Exponential-size neighborhoods for the pickup and-delivery traveling salesman problem. arXiv preprint arXiv:21077.0518) 2021.
Manfred Padberg and Giovanni Rinaldi. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. Society for Industrial and Applied Mathematics, 33(1): 60-100, 1990.
Andrei Paleyes, Mark Pullin, Maren Mahsereci, Neil Lawrence, and Javier Gonzalez. Emulation of physical processes with emukit. Second Workshop on Machine Learning and the Physical Sciences. NeurlPS, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury. Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing Systems, pp- 8026-8037,05 2019.
Yven Potvin and Jean-Mare Rousseau. A parallel route building algorithm for the vehicle routing and scheduling problem with time windows. European Journal of Operational Research, 66(3):31-330, 1993.
Robert C. Prim. Shortest connection networks and some generalizations. The Bell System Technical Journal, 189-) 1957.
11

---

Published as a conference paper at ICLR 2022
Dabbala Raj Reddy. Speech understanding systems: Summary of results of the feve-year research effort at Carnegie-Mellon University. Technical report, Carnegie Mellon University, 1977.
Andrea Saltelli. Making best use of model evaluations to compute sensitivity indices. Computer Physics Communications, 145(2):280-22)) 2002.
Kate Smith. Neural networks for combinatorial optimization: A review of more than a decade of research. INFORMS Journal on Computing. 11(1):15-34, 1999.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems, pp. 5998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10900, 2017.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. /506. 03550600334, 2015.
Pointer networks. arXiv preprint
Chris Voudouris and Edward Tsang, Partial constraint satisfaction problems and guided local search. Technical report, Department of Computer Science, University Essex, 1996.
Christos Voudouris and Edward Tsang. Guided local search and its application to the traveling salesman problem. European Journal of Operational Research, 113(2):469-499 1999.
Minjie Wang. Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang- Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprint arXiv:1909.01335 2019.
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim, Learning improvement heuris- 2020.
tics for solving routing problems. arXiv preprint
12

---

Published as a conference paper at ICLR 2022
A IMPLEMENTATION DETAILS
We conduct all computational experiments on virtual machines using a single core of an Intel Xcon E5-2650 v4 processor, 24 GB of RAM, and single Tesla P100 GPU with 16 GB of VRAM. We evaluate the various approaches one-at-a-time, to ensure they do not compete for computational resources. When evaluating the various approaches, we record actual tours and use a common method of caleulating tour cost and optimality gap, as we found that small discrepancies in cost calculations between implementations led to skewed results. We recommend this approach when comparing different approaches for solving the TSP. Based on approximately 200,000 TSP solutions, we determined that an absolute threshold of 10- on the value of the objective function is sufficient to separate optimal and sub-optimal solutions.
We train our model on sets of one hundred thousand 20, 50, and 100-node Euclidean TSP instances. We generate all instances by uniform-randomle sampling node locations in the unit square [0, 112. We calculate the target output, the regret of including each edge in the solution, according to eq. (4) We use Concorde to find an optimal solution and LKH-3 with 100 trials and 10 runs to solve find optimal solution with given edge fixed. We empirically validate that this configuration for LKH-3 sufficient to find optimal solutions for problems with 100 nodes or less. We scale the input features and target outputs range of [0, 1].
We train our model by minimizing the 12 loss to the target output using the Adam optimizer (Kingma & Ba 2014) and an exponentially decaying learning rate ry = 10-3 x (0.99),, where e is the epoch. We train the model for 100 epochs with early stopping. We use a training batch size B 32 for the 20 and 50-node training sets, and a training batch size of B = 15 for the 100-node training set due to limited GPU memory. Our model uses T 3 message passing layers and our GLS algorithm uses K = 20 perturbation moves. Our approach is implemented using Python 3.8.11, PyTorch 1.9.0 (Paszke et al. 2019). DGL 0.7.1 (Wang et al. 2019), and CUDA 10.2, and is open-source.
We use the open open-source implementation of Kool et al. (2018) with the best configuration, which samples 1280 solutions in parallel. We use this implementation as-is for experiments where com- putation time is not fixed. We modified the implementation until the computation time limit reached for experiments where computation time is fixed. We use the open-source implementation of da Costa et al. (2020) with the best configuration, which uses 2000 iterations. We use this implementation as-is for experiments where computation time is not fixed. We modified the implementation to iterate until the computation time limit is reached for experiments where computation time fixed. We used the open-source implementation of Joshi et al. (2019). We found programming error in their beamsearch implementation that caused invalid tours to be reported. We modified their implementation to detect invalid tours and discarded them when they are produced. Our changes are shown in Listing [ Therefore, our results may differ from those originally reported by the authors.
continuously sample 1280 solutions
13

---

Published as a conference paper at ICLR 2022
Listing 1: Programming enror fix for al. (2019)
diff --git 2. index wttp:l//smmmellttllss.....
b/utils/model_tt p.p.p
+++ s/ttils/modeL_ttilsss 100644
e8 -5,6 +5,12 @e import no from bealsebba import
from utils.graph_utill import
9 +def is (tour) +
nodes set set (tour)
for n in nodes:
if cour.count.ii (n) !- 1:
return False
return True
def 16
___pre__noded y_nodes, node_cx):
17
18
@0 -143,7 7 +149, 12 00 def
x_edges_va vals_,,lue,,, beam_si ze, batc
if hyp len < shortest 1ens iid and is valvi tour hod_snoes,, num_nodes);
shortest_tours
hyp tours [idx]
21
shortest_lens byp_len
22
return shortest_tours
23
24
shortest_tours_iike = shortest torpesttttuuru.puuu numpy () .tolist ()
25
tour_is_valid
((i_vaaaddala for tour in
shortest_tours__t
if not tour_is_valid.all0::
print (shortest_tours, tour tcur_is_valid) valid)
28
return shortest_tours, tour_is_valid
29
31 def
rate (optimizer, ir):
14

---

Published as a conference paper at ICLR 2022
B COMPARISON TO OTHER APPROACHES
B.1 PERFORMANCE CHARTS
Following the guidelines in Accorsi et al. (2021) we measure the mean optimality gap and compu- tation time per instance, while both are unfixed. Figure depicts the performance of the evaluated non-learning and learning based approaches averaged acToss the entire 20, 50, and 100-node prob- lem sets. The axes are scaled so the plots are easily readable. Results that fall outside the plot limits are shown with an arrow pointing towards the horizontal axis the mean computation time. These plots clearly identify Pareto optimal approaches and dominated ones.
Nearest Neighbor
Farthest: Insertion
Joshi et al.
Local Soarch
109
169
Moan optimallt gap
Moan optmaliny
Kool
10
10-2
da Costa
10-3
10-3
1KH-3 Concorde
Amnll et
Ours
10
10a4
10-3
10
10-1
107
10-3
10-2
10-1
10"
101
Mean mpuutation time instance (s)
Mean
time
(s)
(a) TSP20
Neighbur
10a
F Farthesk Insertion
101
Local Search
10a
10a
Kool
Joshi st al.
optmality
opiimallt
O. da Costa et al
10"1
10-1
Aroold
10-4
10-2
Qurs
10-1
Kit-3
10-3
Concorde
10-1
10-4
10-2
10-1
10P
10a
10
10-1
100
10'
Mean computation time per instance (5)
Mean computation time per instance (6)
(b) TSP50
Nearest Nelgabor
Farthest Insertion
10a
10
Local Search
Moan optimality (8)
et
Joshi et
10P
Arnold et
Moan aptimality gap
109
Costa at Our
10-1
10-1
LKB-3
10-4
10-4
10
10-3
Concorde
10-1
10
10-2
10
10'
Mean co computation time per instance (6)
Moan comgutation time per instance (6)
TSP100
Figure 3: Mean optimality gap and computation time per instance for three increasingly difficult problem sets. The left plot shows non-learning based approaches, where the Nearest Neighbour heuristic, LKH-3, and Concorde typically form the Pareto front. The right plot shows learning based approaches, where Kool et al. (2018) and approach form the Pareto front.
15

---

Published as a conference paper at ICLR 2022
B.2 CONVERGENCE PROFILE CHARTS
We evaluate the solution quality, in terms of mean optimality gap and number of problems solved optimally, function of computation time over fixed computation time. The resulting conver- gence profile provides a detailed view of how each approach trades off between solution quality and computation time. Figure 4 depicts convergence profiles for our approach and several recent learn- ing based approaches, for models trained and evaluated on 20, 50, and 100-node problem instances. Computation time required to compute input features, evaluate a model, or to construct an initial solution is visible gap between the trace and the vertical axis, and especially noticeable for Joshi et al. 2019).
100
Moan optimaatty gap (%)
Optimal soluttins Sound
10
60
10-1
100
10
20
95
10
90
Compatation (4)
Compatation timse
Kool et al.
Joshi al.
O. da Costa et
Ours
Con.cordo
(a) TSP20
10a
100
Optimal solutions found (%)
80
Mozn optimality
10a
60
10
10-1
20
10
Compatation time 66)
Comgutation time (4)
Kool et
Joshi al.
O. da Costa et
Ours
Con.corda
(b) TSP50
Oplineal sola Lonc Gound (%)
80
10a
Mean optimalty
60
40
20
10
10
Computation Lime
Computation time
(c) TSP100
Figure 4: Solution quality as function of computation time for three increasingly difficult problem sets, demonstrating that our method converges optimal solutions at faster rate than the evaluated learning based approaches. The left plot shows the mean optimality gap. The right plot shows the percentage of optimally solved problems.
16

---

Published as a conference paper at ICLR 2022
C GENERALIZATION PERFORMANCE
C.I GENERALIZATION TO LARGER INSTANCES
Figure 5 depicts convergence profiles for the learning based approaches when generalizing from smaller problem instances to larger ones. The plots are arranged in order of increasing difference in size between the training and test problem sets.
100
optimality (86
Optimal sabations found
10
40
10a
10
10
Computation
Computation Lime
Joshi al.
Ours
Concorda
(a) Models trained on 20-node TSPs solving the TSP50 problem set.
100
Optinel sodu Eonss Eound (%)
80
Monn optimalty gap
60
10a
20
10
Computation time
Compatation time
Kool et
Joshi at
0. Costa al.
Ours
Concorde
(b) Models trained 50-node TSPs solving the TSP100 problem set.
100
Opt Eini sotations found (%)
Moan optimality (%)
60
40
10a
Computation
time
Computation time
Kool et
Joshi et al.
0. Costa et al.
Ours
Con.oorde
(c) Models trained on 20-node TSPs solving the TSP100 problem set.
Figure 5: Solution quality as function computation time for three increasingly difficult gener- alization tasks, demonstrating that our method is able to generalize from smaller to larger problem instances better than several learning based approaches. The left plot shows the mean optimality gap. The right plot shows the percentage of optimally solved problems.
17

---

C.2 GENERALIZATION TO REAL-WORLD INSTANCES
Published as conference paper at ICLR 2022
In many cases there may be insufficient examples of real-world problem instances to train model, meaning it must be trained on synthetic data. Therefore, it is important to evaluate this "sim-to-real" transfer. Table shows mean optimality gap and computation time for the evaluated learning based methods using models trained on random 1ode TSPs and evaluated on TSPLIB instances with 50 to 200 nodes and 2D Euclidean distances (29 instances).
Method Instance
Kool al.
Joshi et al.
O. da Costa al.
Ours
Time (s)
Gap (%)
Time (s)
Gap (%)
Time (8)
Gap (%)
Time (8)
Gap (%)
eil51
0.125=
1628=00125
3.026=0.012
8.339=0.000
28.051 .40
0.067+0.099
10.074:0.066
0.000=0,000
berlin52
0.129
4.169+1.289
3.068=0.022
33.22550.000
31.87420.388
0,449+0.42
10.103+0.,08
0.142=0.000
st70
0.200:0.000
1.737=0.093
4.037=0.009
24.785:0.000
23.964+0.12 122
0.040=0.00$
10.053+0.078
0.764=0.000
ei176
0.225=0.000
1.992=0.004
4.303=0.021
27.411#0.000
26.551+0.065
0.096=0.237
10.155+0.067
0.163++0000
pr76
0.226+00002
0.816=0.130
4.378=0.023
27.793+0.000
39,485=0.152
1.228++.900
10.049=0.023
0.039=0,000
rat99
0.347=0.000
2.645=0.103
5.559=0.016
17.633+0.000
32.188+0.064
0.123=0.000
9,948=0.013
0.550=0,000
kroA100
0.352++0.00
4.017=0.043
5.705=0.018
28. 28.828000000
42.095=0.100
18.31320.000
10.255++.0045
0.728=0,000
kroB:100
0.352+0..00
5.142=0.269
5.712+0.018
34. 686000000000
35.10740.078
1.119+00060
10.317+0.150
0.147=0.000
kroC100
0.352*0..01
0.972=00005
5.641=0.013
55.506+0.000
34.333+0.168
0.349=0.191
10.172++0.208
1.571
kroD100
0.352+0.000
2.717=0-327
5.621=0.024
38.018=0.000
25.772+0.090
0.866+00447
10.375+0.155
0.572+0.000
kroE100
0.352+0.000
1.470=0.109
5.650=0.026
26.589#0.000
34.475+0.166
1.832+0
10.270#0.171
1.216=00000
rd100
0.352+0.000
3.407=0.092
5.737=0.033
50.432+0.000
28.963+0.077
0.003#0.005
10.125+0.039
0,459=0.000
18
eil101
0.359+0.001
2.994=0.2.0
5.790=0.018
26. 70.00100.000
0.387+0.096
10.276=000.36
0.201=0.000
lin
0.380
1.739=0.125
5. 0.948
34 44.90200.000
19.51110.145
1.8670.644
10.330+0.037
0.606=0.000
pr107
0.391=0.001
3.933+0.352
0.944
80.564+0.000
29.039+0.100
0.89
9.977=0.050
0.439=00000
pr124
0.499=0.002
3.677=0.523
7.059=0.031
70. 1,6+0.0000
29. 570+0.038
10.32244.603
10.360=0.190
0.755=0.000
bicr127
0.220
0.90
7.242+0.022
45. 00.000000000
39,029+0.144
3.044+0.272
10.260=0.124
1.948=0,000
ch130
0.550
3.18220.182
0.351=0.074
39.090=0.000
34,43620.16
0.709:0.762
10.032+0.063
3.519
pr136
0.585+0.000
5.064=0.998
7.727=00026
58.673+0.000
31 31.056+0.081
0.000=0.000
10.379+0.077
3.387=0.000
pr144
0.63810.001
7.641=0.516
8.132+0.017
55.837+0.000
28.913+0.093
1.526:0.276
10.276:20.000
3.501=0.000
ch150
0.697=0.002
4.584=0.324
8.546=0.048
49.743+0.000
45.407..1177
0.312+0.084
10.109=0.060
2. 2.113+0.000
kroA 150
0.695=0.001
3.784=0.336
8,400=00177
45.411+00000
29. 99.399
0.724=0. 1988
10.331+0.281
2.984
kroB150
0.69620.002
2.437=0.188
8.573=0.021
56.745+0.000
29.005+0.071
0.886:0.347
10.018+0.103
3,258+0.000
pr152
0.708=0.001
7.494=0.265
8.632+0.035
33.925+0.000
29.003+0.10 106
0.029=0.018
10.267+0.096
3.119900000
u159
0.764=0.001
7.551+1.581
9.012+0.019
38. 08.338+0.000
28.961=0.096
0.054=0.000
10.428+0.078
1.020=0,000
1at
1.11420.003
6,893+0.505
11.23620.028
24.968+0.000
34.425+0.054
0.743+0.312
12.295+0.087
1.66620,000
d198
1.153=0.052
373.020+45.415
11.519%0.091
62.351+0.000
30.864+0.066
0.522+0.297
12.596+0.043
4.772+00000
kroA200
1.150=2.000
7.106=0.391
11.702#0.036
40,885+0.000
33.832+0.402
1.441=0.068
11.088+0.075
2.029+0.000
kroB200
1.150=0.001
8.541=0.565
11.689+0.041
43.643+0.000
31.951+0.128
2.064+0.419
11.267#0.245
2.589+0.000
Mcan
0.532+0.300
16.767=67.953
7.000#2.415
40.025+15.702
31.766+4.543
1.725+3.767
10.420+0.630
1.529+1.328
Table 3: Solution quality and computation time for for learning based methods using a model trained on random 100-node problems and evaluated on TSPLIB
instances with 50 to 200 nodes and 2D) Euclidean distances. Means and standard deviations are reported, calculated across 10 runs per problem instance. Pareto optimal values (i.e. faster better solutions) are bolded.

---

Published as a conference paper at ICLR 2022
D ANALYSIS OF ADDITIONAL INPUT FEATURES
We evaluate the potential benefit of adding additional features to our regret approximation model. While more features can help produce better predictions, they come at the cost of additional compu- tation time. We consider a total of ten additional features, described in Table 4 We use a Gaussian process-based surrogate model to conduct global sensitivity analysis (Gratiet et al. 2016) of the input features on the validation loss of the model after training. We assume that better regret predic- tions will equate to better guidance by the GLS algorithm, ultimately resulting in better performance to the problem sets.
Name
Description
Complexity
Perpendicular distance from a node to a line from the depot node through the centroid of the nodes (Amold & Sörensen 2019b).
Node width
((n)
Edge width
Absolute difference between the width of two nodes.
O
Depot weight
Weight from a node to the depot node.
(n))
where node is the k-nearest neighbor of i. 'Theee two features for a given edge, the rank of w.n.. j and the rank of j w.r.t. i.
Neighbor rank
O(n²)
If the edge is part of the k-nearest neighbor graph, where k is 0.3n.
30%-NN graph
O(n²)
If the edge is part of the k-nearest neighbor graph, where l 0.2n.
20%-NN graph
O
If the edge is part of the k-nearest neighbor graph, where k 0. In.
10%-NN graph
If the edge is part of the minimum spanning tree, calculated using Prim's i algorithm (Prim) 1957).
MST
O(n²)
If the edge is part of solution constructed by the nearest
NN solution
(n)
neighbor hcuristic.
If the edge is part of solution constructed by the nearest insertion heuristic.
NI solution
O
Table 4: Summary of additional input features evaluated. While more features can help produce better predictions, and thus better guidance for the GLS algorithm, they come at the cost of additional computation time.
We semi-randomly sample 100 input feature sets using Latin hypercube sampling (McKay et al. 1979). We train a model using each of these feature sets for 35 epochs without early stopping and record the final validation loss. Using these results, we fit Gaussian process to emulate the mapping between the feature set F = f1,..,, f10), and the validation loss achieved by our model after training, where fn indicates whether or not feature is used. We then compute Monte-Carib estimates of the main and total effects of each input feature on the model's validation loss (Saltelli 2002). Our implementation uses Emukit (Paleyes al. 2019). F effect for each input feature. Edge weight is the most important feature, followed by neighbor rank, depot weight, edge width, and node width. The remaining features have little to no importance.
the estimated total
We train model using these top five features on 20-node problems and compare its performance to the equivalent model using edge weight as the only feature when solving the 20, 50, and 100- node problem sets. The performance of both models at the computation time limit is shown in Table [ While the model using additional input features produces slightly more accurate regret predictions, any benefit is cancelled out by the additional time required to compute these features. Note that the results are slightly different from those reported in Figure due to different training hyperparameters.
19

---

Published as a conference paper at ICLR 2022
Estimated total effect
10% NN graph
NI solution
NN salution
20% NN graph
30% NN graph
MST
Nade width
Edge width
Depot weight
Neighbour rank
Edge weight
Figure 6: The estimated total effect of edge weight and ten additional features model validation loss after training based on 100 randomly-sampled feature sets, using Gaussian process- global sensitivity analysis. A small effect implies that the feature is not important when predicting regret, and vice-versa.
Problem
Method
Optimality gap (%)
Optimal solutions (%
Local search only Edge weight only
1.824+3.255 252
54. 7000
TSP20
0.000=0.000
100.0000
Top 5 features
0.000=0.003
99.9000
Local search only Edge weight only Top 5 features
3.357+2.602
6.4000
TSP50
0.082+0.255
82.1000
0.080=0.295
83.2000
Local search only Edge weight only Top 5 features
4.16942.046
0.3000
TSP100
2.183+1.383
2.2000
2.228
2.2000
Table Ablation analysis of our method using local search alone (no guidance). model using edge weight alone, and model using additional features. Both models are trained on 20-node problems and evaluated on the 20, 50, and 100-node problem sets. The mean optimality gap and standard deviation, well as the percentage of optimally solved problems are reported after 10 seconds of computation time per instance. While the model using additional input features produces slightly more accurate regret predictions, any benefit is cancelled out by the additional time required to compute these features.
20


Reviews:
[{"review_id": "pFMAzOIn1DC", "reviewer": "Reviewer_v3Sn", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In recent years, methods for the TSP have paid little attention to the fairness of the evaluation criterion, and this paper achieved a good performance under the improved evaluation method. But I suppose the experiment should be more comprehensive.\n\nPros: \n \n1. The author used edge length as the feature when designing the network, and analyzed the pros and cons of each network in detail in the Discuss section. Such detailed analysis is extremely necessary.\n \n2. They chose a better way to evaluate, which is valuable, because the evaluation methods in recent years lack in this respect. The previous evaluation method is easy to find a loophole. \n\nCons: \n \n1.\tThe ablation study is not detailed enough. The method proposed by the author is based on GLS, but uses LS as the baseline, and the experimental do not show which part of the method contributes more.\n\n2.\tThe number of cities considered by recent methods is getting larger and larger, far more than 100. So how does the method proposed by the author perform on instances with a larger number of cities, such as 500. Will Global regret become unpredictable?\n\n", "summary_of_the_paper": "This paper proposed an approach for solving TSP, using GLS guided by global regret, and designed a neural network to predict the regret. The authors evaluates the performance of each method by calculating gap between the prediction and the global optimum in a fixed computation time.", "summary_of_the_review": "The contribution of the paper is significant and somewhat new with insights into the TSP problem by GNN.", "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": "MFdO0I_Q5kO", "reviewer": "Reviewer_aECP", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and presents an interesting approach to solving TSP that can outperform some other existing approaches. The structure is appropriate, there is a very good review of related works, good description of the method, experiments, and results. There are also extensive supplementary materials. The introduced method is novel, might be significant, and the quality of this article seems to be on-par with other papers applying ML techniques to solve TSP published at top-tier conferences (which are also cited in this paper). The only weakness I see is the way of presenting the results in Fig. 3. All the percentages of optimally solved problems are relatively low, so the plots for some algorithms are not clearly visible (however, it is clear that the introduced algorithm outperforms other approaches). I recommend acceptance of this article.", "summary_of_the_paper": "The paper presents a hybrid data-driven approach for solving the TSP based on Graph Neural Networks and Guided Local Search. The model predicts the regret of including each edge of the problem graph in the solution; GLS uses these predictions in conjunction with the original problem graph to find solutions. The experiments demonstrate that this approach converges to optimal solutions at a faster rate than state-of-the-art learning-based approaches and non-learning GLS algorithms for the TSP, finding optimal solutions to 96% of the 50-node problem set, 7% more than the next best benchmark, and to 20% of the 100-node problem set, 4.5× more than the next best benchmark. When generalizing from 20-node problems to the 100-node problem set, this approach finds solutions with an average optimality gap of 2.5%, a 10× improvement over the next best learning-based benchmark.", "summary_of_the_review": "The paper is well-written and presents an interesting approach to solving TSP that can outperform some other existing approaches. The structure is appropriate, there is a very good review of related works, good description of the method, experiments, and results. There are also extensive supplementary materials. The introduced method is novel, might be significant, and the quality of this article seems to be on-par with other papers applying ML techniques to solve TSP published at top-tier conferences (which are also cited in this paper). The only weakness I see is the way of presenting the results in Fig. 3. All the percentages of optimally solved problems are relatively low, so the plots for some algorithms are not clearly visible (however, it is clear that the introduced algorithm outperforms other approaches). I recommend acceptance of this article.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MEgTF9Zayw", "reviewer": "Reviewer_u4N8", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Pros:\n\n1. The paper is well-written and easy to follow. \n\n2. Hybridizing machine learning with local search is an interesting approach.\n\n3. The experimental results show that the proposed algorithm outperforms other recently published learning-based algorithms, which is nice.  \n \n\nCons: \n\n1. The motivation of this work is not strong enough. The paper is motivated by \"solving large TSP instances quickly without sacrificing solution quality remains challenging for current approximate algorithms\". Since there exist exact solvers such as Concorde that can solve large-scale TSPs quite efficiently, the authors should further justify why improving approximate algorithms for TSP is interesting. \n \n2. The motivation is not well-supported by the experiments. The paper only presents the results for TSP up to 100 nodes, and no evidence is provided to show that the method can perform well for large-scale TSPs.\n \n3. Only learning-based methods and a weak baseline GLS are compared in this paper. Some effective traditional methods for TSP such as LKH are missing. The exact method Concorde should also be compared since it is generally very fast for solving TSP instances with a few hundred nodes.  \n\n4. The proposed method is only evaluated on randomly generated instances. In literature, there are standard benchmark instances such as those collected in the TSP library, which are much harder than randomly generated instances. The proposed method should also be evaluated on standard benchmark instances in order to show its efficacy.\n", "summary_of_the_paper": "The paper presents a machine learning approach to improve Guided Local Search (GLS) for finding high-quality solutions for the Travelling Salesman Problem (TSP). Specifically, the paper proposes to use an ML model to predict the global regret for an edge, i.e., the difference in the objective values of a locally optimal solution with that edge being included and a globally optimal solution. Then, the prediction is used to guide the GLS to escape local optimal solutions. \n", "summary_of_the_review": "Although the paper shows some improvements over several learning-based methods on small TSP instances, more comparison between the proposed method and effective traditional algorithms on large-scale TSP instances is required in order to support the claim of the paper.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9yfjoU_5yFI", "reviewer": "Reviewer_2Y2p", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "# 1. Strengths\n\n1.1. To the best of my knowledge, this is the first work on **combining deep learning with a metaheuristic** (GLS).  The proposed idea of using a GNN to learn the global regret to guide the LS + GLS search procedure  is novel and interesting.\n\n1.2. The approach of **operating on the line graph of routing problems** like TSP is somewhat novel (but may need to be better contextualized + ablated, see suggestions below). This is potentially more principled than the prevalent approach of encoding node coordinates, which does not account for the underlying symmetries of routing problems. The discussion on this aspect in Section 6 is thought-provoking.\n\n1.3. The paper proposes a new evaluation setup, which aims to **evaluate trade-offs between solution quality and time**. This effort to move away from somewhat simplistic evaluations on fixed TSP sizes without a time limit is appreciated, as it provides more depth to the results. A caveat is that I do have some issues with the proposed setup that need to be addressed (see below).\n\n---\n\n# 2. Weaknesses & Things to be addressed\n\n## 2.1. On evaluation setup:\n- 2.1.1. I agree with the authors that the current style of evaluating deep learning approaches for TSP/routing has several pitfalls and does not give the full picture. Thus, I do appreciate their introduction of a fixed computation time budget per test instance and %-age of optimally solved instances into the picture. The evaluation of deep learning approaches for routing has recently been questioned by the community, too [8, 9].\n- 2.1.2. **How to contextualize empirical improvements without standard setup?**: The current set of experiments and choice of baselines did not convince me sufficiently about the empirical improvements being brought about by the novel methodology, as recent papers have significantly improved over Kool-etal, Joshi-etal, e.g. [5, 6, 7]. In addition to the proposed evaluation setup, I would still have liked to see the paper compare to existing literature in the conventional format of reporting optimality gap, tour length and total inference time for 10000 instances of TSP20, 50 and 100. Alternatively, the paper could consider showing results for generalization to real-world TSPLib instances, for which many recent papers are providing tour lengths per instance.\n- 2.1.3. **Why fix batch size = 1?**: One of the major advantages of deep learning approaches for combinatorial problems is the ability to perform batched inference. Thus, it was difficult for me to understand why the paper chose to set batch size = 1 during the evaluation, especially as the motivation was real-time inference. Is it possible to implement a batched variant of LS + GSL, or is it a sequential algorithm? Is the search procedure run on the GPU or the CPU?\n- 2.1.4. **Why not use beam search in under 10s?**: The extremely poor results for Joshi-etal + Sampling on TSP100 are surprising, as the original paper reported optimality gaps 1.5-2%. I believe it is important to fairly compare to this work as it is most related in terms of methodology (see my comments on related work). Can you also show results for the original formulation (i.e. beam search) of their method? (Based on the results and computational times they have reported, the beam search is critical for getting the model to work and should take <10s per instance, too.)  \n- 2.1.5. **Why not include classical baselines**: Once again, I believe that the Concorde solver can very easily solve small TSP100 to optimiality within 10s per instance (in fact, I am sure it would be under 1s). Similarly, the LKH-3 heuristic is also not taking longer than 10s per instance. I think it is critical to compare to these classical and well known baselines.\n\n## 2.2. On missing latest related work and comparisons:\n- 2.2.1. **Missing one-shot deep learning approaches**: Within the ‘ML alone provides a solution/provides information to an OR algorithm’ sub-section, there are works with sequentially built solutions [2, 3] and those that output the solution in one-shot [4]. I believe this paper is in the second camp: similar to Joshi-etal [4], the neural network outputs predictions over edges, which are then used to build a solution via a classical search algorithm. Thus, it is critical to also contextualize how the specific search algorithm used in this work (LS + GLS) compares to recent/concurrent advances on top of Joshi-etal’s model: e.g. leveraging dynamic programming [5] or MCTS [6] to replace the original beam search.\n- 2.2.2. **Missing sequential approach POMO**: An important reference that is missing is POMO [7], a recent NeurIPS paper which can be considered an update to Kool-etal [3] from the lense of symmetries in solutions for routing problems. Including POMO in the related work + potentially in the experimental comparisons will further strengthen the paper. POMO should also be discussed in the Discussions section at the end of the paper regarding its use of symmetries, and how it may be different from the proposed approach.\n\n## 2.3. Missing generalization to other problems\nAn important limitation which, to the credit of the authors, is openly pointed to is that the work only shows results for TSP. The paper would be significantly strengthened by demonstrating at least some degree of generality of the proposed approach, e.g. CVPR could be the first candidate. It is not convincing to simply say that the method can be applied. (Although I do understand that this may be challenging to show convincingly within the rebuttal period.) \n\n---\n\n# 3. Other minor comments and suggestions\n\n## 3.1. On message-passing over line graphs vs. message-passing over nodes and edge features: \n- 3.1.1. **Wrong claim?**: It may be worth expanding on how different it is to do GNN/message passing over the transformed line graph (as in this work) vs. message passing over the original graph while also including and updating features over edges (as proposed in [4] and adapted by [5, 6]). This has also been done in other application domains, e.g. the famous ChemProp model. The claim that *‘most approaches to edge-property prediction predict the properties of an edge as a function of the surrounding node states’* may not be true, as [4, 5, 6] are explicitly using the edge features to make predictions.  \n- 3.1.2. **Missing ablation**: Currently, the empirical evaluation only shows results for the entire line-graph GNN + GLS technique. In order to ablate the impact of the line graph transformation and the significance of the proposed GNN architecture, it may be useful to show experiments on replacing the proposed line-graph GNN with: (1) GNN on original graph w/ and w/out edge feature updates; (2) simple MLP applied to each graph edge’s original feature.\n\n## 3.2. On motivation for this work: \n- 3.2.1. In the abstract, the major motivations for the proposed techniques is to approximately solve large-scale TSP instances **and** to provide solutions in real-time without sacrificing solution quality.\n- 3.2.2. **Generalization to real-world sizes**: More experiments on scalability of training or zero-shot genreralization to TSPs bigger than 100 nodes or on real-world instances from TSPLib would make the claims more convincing.\n- 3.2.3. **Real-time and fast routing solvers**: The introduction briefly mentions that this remains a challenge for current algorithms which do not regard computation time. To make this claim stronger, it may be useful to point out how real-time routing problems are typically being solved in industry and why there exists a research gap that this paper is attempting to fill. (e.g. KGLS [1] exists but is it requiring a lot of handcrafting?)\n\n## 3.3. On scalability of dataset generation: \nIt was noted in [8] that generating supervised datasets is a limitation in scaling up, as building these datasets itself can be computationally challenging for real-world problem scales beyond 100s of nodes. Isn’t developing the training datasets for your approach further more cumbersome than previous supervised approaches, e.g. your approach requires running Concorde as well as multiple runs of LKH3. Is this approach scalable beyond small TSP100 instances (especially considering that one may need more training data to train on harder problems)?\n\n## 3.4. On style of reporting empirical results: \nI personally found the style of reporting performance improvements in the abstract and contributions bullets in the introduction to be rather confusing. I would suggest that the paper sticks to either using percentage improvements (x% improvement over y), times improvements (x times improvement over y), but not using both. It could even be simpler and more informative to rephrase something like ‘we reduce the average optimality gap on TSPn from x_1 to x_2, a y times/%-age improvement’. This will help experts contextualize the results immediately.\n\n---\n\n# References\n\n[1] Florian Arnold and Kenneth Sorensen. Knowledge-guided local search for the vehicle routing problem. Computers & Operations Research, 105:32–46, 2019.\n\n[2] Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the TSP by policy gradient. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 170–181, 2018.\n\n[3] Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475, 2018.\n\n[4] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227, 2019.\n\n[5] Wouter Kool, Herke van Hoof, Joaquim Gromicho, Max Welling. Deep Policy Dynamic Programming for Vehicle Routing Problems. arXiv preprint, 2021.\n\n[6] Zhang-Hua Fu, Kai-Bin Qiu, Hongyuan Zha. Generalize a small pretrained model to arbitrarily large tsp instances. AAAI 2021. \n\n[7] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, Seungjai Min. POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. NeurIPS 2020.\n\n[8] Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, Thomas Laurent. Learning TSP Requires Rethinking Generalization. CP 2021.\n\n[9] Luca Accorsi, Andrea Lodi, Daniele Vigo. Guidelines for the Computational Testing of Machine Learning approaches to Vehicle Routing Problems. arXiv preprint, 2021.\n", "summary_of_the_paper": "This paper proposes a novel deep learning + guided local search heuristic technique for approximately solving the Travelling Salesperson Problem (TSP). This research direction is **well motivated**, as inexpensive but approximate heuristics to graph combinatorial optimization problems such as TSP are promising for enabling real-time applications in vehicle routing and operations research.\n\nFrom a methodological perspective, the paper’s major contribution is to develop and train a **Graph Neural Network (GNN) on line graphs** for approximating the ‘regret’ of including graph edges in TSP solutions. The use of regret per edge is novel; regret is a metric used in the metaheuristic **Guided Local Search (GLS)**. After the GNN is trained, the proposed technique starts from a greedy solution and uses a TSP-specific Local Search interleaved with the **‘learnt’ GLS metaheuristic** to arrive at the final solution.\n\nFrom an empirical point of view, this work proposes a **new evaluation setup** to measure solution quality of TSP heuristics within a fixed computational time. Their GNN + GLS approach outperforms popular learnt baselines and handcrafted GLS in this setup for TSPs up to 100 nodes.", "summary_of_the_review": "I recommend that this paper is currently **marginally below the acceptance threshold**. Overall,  I found the methodological ideas (learning-guided metaheuristics + GNNs on line graphs to respect the symmetry of combinatorial problems) to be both novel and interesting. However, I have major issues with the **lack of extensive experimental evaluation**. In particular, the experiments are insufficient to convince the reader that the proposed methodology leads to significant empirical improvements over recent works, or can generalize to real-time routing problems beyond the TSP. It is also difficult to contextualize this paper’s results as the evaluation setup is not conventional and comparissons to classical baselines like Concorde and LKH3 are absent. While the new setup may be a step in a positive direction, additional results **comparing to the latest published work** [6,7] in a conventional format or generalization to real-world and **larger scale TSPLib instances** would be needed for me to be convinced to improve my score. If the major motivation for the work is to tackle large-scale routing problems in real-time, demonstrating that the proposed techniques work on TSPs larger than just 100 cities and on non-random distributions is also important.\n\n---\n\n# Update after rebuttal\n\nI appreciate the updates to the evaluation setup and the reported results. I also appreciate the inclusion of TSPLib experiments and discussions on recent literature [5,6,7,9]. Most of my concerns are addressed, and I am happy to **raise my score to an accept** after the authors provided clarifications to the newly introduced changes (discussed below in the comments).\n\nI believe this work is **bringing new methodological ideas** to the literature on learning-driven combinatorial optimization and will be of interest to the community. However, I am still lukewarm because the motivation of the work is to tackle real-time routing problems with non-standard constraints, but the **empirical results are only shown for TSP**. In the paper's present state, it is not clear to me whether this approach will generalize to other routing problems, especially those problems with more challenging constraints for which generating labelled training datasets is an issue.", "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": "-iRsg5HwQY", "reviewer": "Reviewer_un7S", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I like about the submission that it goes beyond simply trying to learn optimum solutions using GNNs. Instead, it learns optimum TSP solutions, uses that to approximate the consequences of adding an edge to the solution, thus guiding a local search procedure. In that regard, it could be regarded as a sophisticated local search rather than an ML approach. \n\nThe main concern I have with the submission is that it states that combinatorial approaches, e.g. from the operations research community, are focused on computing optimum solutions and have little regard for computation time. This is, in my view, not true: Any classical branch-and-bound approach may be run in heuristic mode where it is stopped after a couple of seconds. While this will clearly not guarantee an optimum solution, it will quickly provide a good solutions, since B&B approaches tend to spend most of their running time proving optimality and typically find a good solutions at the very beginning of their execution. As opposed to what the submission states in the introduction, these algorithms will provide a quality guarantee (something that this approach does not), just not a global one. Setting such a timelimit provides precisely the tradeoff between computation time and quality (guarantee) that this submission claims. These algorithms work on instances with millions of nodes, whereas this submission considers instances with 100 nodes. \n\nEven is that is not desired: The Euclidean TSP may be approximated in polynomial time with an error that is arbitrarily close to 1 (Arora, J. of the ACM, 1998). Along more practical lines, Christofides' heuristic quickly yields a 3/2-approximate solution. \n\nThese algorithms could be included in the experiments as a reference. The OR community uses the TSPLib benchmark set to evaluate TSP algorithms. I am not convinced that the randomly generated instances in this submission are difficult and would like to see solution time/quality of a simple greedy nearest neighbor heuristic. ", "summary_of_the_paper": "The submission is concerned with developing a heuristic for the traveling salesperson problem (TSP) using graph neural networks an dguided local search. The idea of the approach is to learn the regret incurred by including an edge into the solution and to use this to guide a local search out of local optima. As opposed to previous work, the regret is computed against the global optimum (which is approximated by learning). The submission is limited to the Euclidean TSP variant where we operate on a complete graph whose edge weights are given by Euclidean distances.", "summary_of_the_review": "In my view, the submission fails to compare against the large body of existing literature for the TSP problem and ignores standard benchmark sets. I do not share the submissions view that the Concorde solver and various heuristics are geared towards finding optimum solutions only. I would also like to point out that there are algorithms that do provide quality guarantees. That being said, I am not sure what ML brings to the table here.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, a novel machine learning-based method for solving TSP is presented; this method uses guided local search in conjunction with a graph neural network, which is trained to predict regret. Reviewers disagree rather sharply on the merits of the paper. Three reviewers think that the paper is novel, interesting, and has good empirical results. Two reviewers think that the fact the results are not competitive with the best non-learning-based ("classic") solvers mean that the paper should be rejected.
This area chair believes that research is fundamentally not about beating benchmarks, but about new, interesting, and sound ideas. The conceptual novelty of this method, together with the good results compared with other learning-based methods, is sufficient for accepting the paper.
Decision: Accept (Poster)