Targeted sampling of enlarged neighborhood via Monte Carlo tree search for TSP
Authors: Zhang-Hua Fu
Kai-Bin Qiu
Meng Qiu
Hongyuan Zha
Venue:  (2020)
Keywords: Travelling salesman problem
Monte Carlo tree search
Reinforcement learning
Variable neighborhood search

Abstract: The travelling salesman problem (TSP) is a well-known combinatorial optimization problem with a variety of real-life applications. We tackle TSP by incorporating machine learning methodology and leveraging the variable neighborhood search strategy. More precisely, the search process is considered as a Markov decision process (MDP), where a 2-opt local search is used to search within a small neighborhood, while a Monte Carlo tree search (MCTS) method (which iterates through simulation, selection and back-propagation steps), is used to sample a number of targeted actions within an enlarged neighborhood. This new paradigm clearly distinguishes itself from the existing machine learning (ML) based paradigms for solving the TSP, which either uses an end-to-end ML model, or simply applies traditional techniques after ML for post optimization. Experiments based on two public data sets show that, our approach clearly dominates all the existing learning based TSP algorithms in terms of performance, demonstrating its high potential on the TSP. More importantly, as a general framework without complicated hand-crafted rules, it can be readily extended to many other combinatorial optimization problems.

Under review as a conference paper at ICLR 2020
TARGETED SAMPLING OF ENLARGED NEIGHBORHOOD VIA MONTE CARLO TREE SEARCH FOR TSP
Anonymous authors Paper under double-blind review
ABSTRACT
The travelling salesman problem (TSP) is well-known combinatorial optimiza- tion problem with a variety of real-life applications. We tackle TSP by incorpo- rating machine learning methodology and leveraging the variable neighborhood search strategy. More precisely. the search process is considered as a Markov decision process (MDP), where 2-opt local search used to search within a small neighborhood, while Monte Carlo tree search (MCTS) method (which iterates through simulation, selection and proppppopngttion steps), is used sam- ple a number of targeted actions within an enlarged neighborhood. This new paradigm clearly distinguishes itself from the existing machine learning (ML) based paradigms for solving the TSP, which either uses end-to-end ML model, or simply applies traditional techniques after ML for post optimization. Experi- ments based on two public data sets show that, approach clearly dominates all the existing learning based TSP algorithms in terms performance, demon- strating its high potential on the TSP. More importantly, general framework without complicated hand-crafted rules, it can be readily extended to many other combinatorial optimization problems.
INTRODUCTION
The travelling salesman problem (TSP) is a well-known combinatorial optimization problem with various real-life applications, such as transportation, logistics, biology, circuit design. Given n cities as well as the distance dij between each pair of cities and j. the TSP aims to find cheapest tour which starts from a beginning city (arbitrarily chosen), visits each city exactly once, and finally returns to the beginning city. This problem is NP-hard, thus being extremely difficult from the viewpoint of theoretical computer science.
Due to its importance in both theory and practice, many algorithms have been developed for the TSP, mostly based on traditional operations research (OR) methods. Among the existing TSP algorithms, the best exact solver Concorde (Applegate al. 2009) succeeded in demonstrating optimality of an Euclidean TSP instance with 85,900 cities, while the leading heuristics (Helsgaun) (017) and TTallard & Helsgaun 2019) are capable of obtaining near-optimal solutions for instances with mil- lions of cities. However, these algorithms are very complicated, which generally consist of many hand-crafted rules and heavily rely on expert knowledge, thus being difficult to generalize other combinatorial optimization problems.
To overcome those limitations, recent years have seen number of ML based algorithms being proposed for the TSP (briefly reviewed in the next section), which attempt to automate the search process by learning mechanisms. This type of methods do not rely on expert knowledge, can be easily generalized to various combinatorial optimization problems, thus become promising research direction at the intersection of MI. and OR. For the TSP, existing MI. based algorithms can be roughly classified into two paradigms, i.e.: (I) End-to-end ML paradigm which uses ML model alone to directly convert the input instance to a solution. (2) ML followed by OR paradigm which applies MI at first to provide some additional information, to guide the following OR procedure towards promising regions.
Despite its high potential, for the TSP, existing ML based methods still in its infancy, struggling to solve instances with more than 100 cities, leaving much room for further improvement compared with traditional methods. To this end, we propose a novel framework by combining Monte Carlo

---

Under review as a conference paper at ICLR 2020
tree search (MCTS) with basic OR method (2-opt based local search) using variable neighborhood strategy to solve the TSP. The main contributions are summarized as follows.
Framework: We propose new paradigm which combines OR and ML using variable neighborhood strategy. Starting from an initial state, a basic 2-opt based local search is firstly used to search within small neighborhood. When no improvement is possible within the small neighborhood, the search turns into an enlarged neighborhood, where a reinforcement learning (RL) based method is used to identify sample of promising ac- tions, and iteratively choose one action to apply. Under this new paradigm. OR and ML respectively work within disjoint space, being flexible and targeted, and clearly different from the two paradigms mentioned above. More importantly, as a general framework with- out complicated hand-crafted rules, this framework could not only be applied to the TSP, but also be easily extended to many other combinatorial optimization problems.
Methodology: When we search within an enlarged neighborhood, it is infeasible to enu- merate all the actions. We then seek to sample a number of promising actions. To do this automatically, we implement a MCTS method which iterates through simulation, selection and propaaatoon steps, to collect useful information that guides the sampling process.
To the best of our knowledge, there is only one existing paper (Shimomura & Takashima (016) which also uses MCTS solve the TSP. However, their method is a constructive approach, where each state is a partial TSP tour, and each action adds a city to increase the partial tour, until forming complete tour. By contrast, our MCTS method is a conversion based approach, where each state is complete TSP tour, and each action converts the orig- inal state to new state (also complete TSP tour). The methodology and implementation details of our MCTS are very different from the MCTS method developed in (Shimomura) & Takashima 2016).
We carry out experiments on two sets of public TSP instances. Experimental results (detailed in Section 4 show that, on both data sets MCTS algorithm obtains (within reasonable time) statistically much better results with respect to all the existing learning based algorithms. These results clearly indicate the potential of our new method for solving the TSP.
Results:
The rest of this paper is organized as follows: methods on the TSP. Section]Jessrrble in detail the new paradigm and the MCTS method. Section provides and analyzes the experimental results. Finally Section concludes this paper.
Section 2 briefly reviews the existing learning based
RELATED WORKS
In this section, we briefly review the existing ML based algorithms on the TSP, and then extend to several other highly related problems. Non-learned methods are omitted, and interested read- ers please find in (Applegate et al., 2009). (Rego et al. 2011). (Helsgaun 2017) and (Taillard & Helsgaun 2019) for overlook of the leading TSP algorithms.
The idea of applying ML to solve the TSP is not new, dated back to several decades ago. Hop- field & Tank (1985) proposed Hopfield-network, which achieved the best TSP solutions at that time. Encouraged by this progress, neural networks were subsequently applied on many related problems (surveyed by Smith (1999). However, these early attempts only achieved limited suc- cess, with respect to other state-of of-he-r algorithms, possibly due to the lack of nigh-performance hardware and training data. In recent years, benefited from the rapidly improving hardware and exponentially increasing data, MI. (especially deep learning) achieved great successes in the field of artificial intelligence. Motivated by these successes, MI. hecomes again a hot and promising topic for combinatorial optimization, especially for the TSP. A number of ML based algorithms have been developed for the TSP, which can be roughly classified into two paradigms (possibly with overlaps).
End-to-end ML paradigm: Vinyals et al. (2015) introduced pointer network which consists of an encoder and decoder, both using recurrent neural network (RNN). The encoder parses each TSP city into embedding, and then the decoder uses attention model to predict the probability distribution over the candidate (unvisited) cities. This process is repeated to choose a city one by one, until forming complete TSP tour. The biggest advantage of the pointer network is its ability of
2

---

Under review as a conference paper at ICLR 2020
processing graphs with different sizes. However, as a supervised learning (SL) method, it requires large number of pre-computed optimal (at least high-quality) TSP solutions, being unaffordable for large-scale instances. To overcome this drawback, several successors chose reinforcement learning (RL.) instead of SI., thus avoiding the requirement of pre-computed solutions. For example, [Bel-] lo et al.] (217)) implemented actor-critic RI. architecture, which uses the solution quality (tour length) as reward signal, to guide the search towards promising area. Khalil et al. (0117) proposed framework which maintains a partial tour and repeatedly calls a RL based model select the most relevant city to add to the partial tour, until forming complete tour. |Emami & Ranka (2018) also implemented an actor-critic neural network, and chose Sinkhorn policy gradient to learn policies by approximating double stochastic matrix. Concurrently. Deudon et al. (2018) and Kool et al. (2019) both proposed graph attention network (GAN), which incorporates attention mechanism with RL. to auto-regressively improve the quality of the obtained solution.
Deeudon
Specifically, [Shimomura & Takashima (20T6) proposed a MCTS algorithm for the TSP, which also belongs to this paradigm. As explained in the introduction section, this existing method is clearly different from our MCTS algorithm (detailed Section 3.5
ML followed by OR paradigm: Applying ML alone is difficult to achieve satisfactory perfor- mance, thus it is recommended to combine ML and OR to form hybrid algorithms (Bengio et al. 2018). Following this idea, NNwak al. (017)) proposed supervised approach, which trains graph neural network (GNN) to predict an adjacency matrix (heat map) over the cities, and then attempts convert the adjacency matrix feasible TSP tour by beam search (OR based method). Joshi et al. (2019) followed this framework, but chose deep graph convolutional networks (GCN) instead of GNN build heat map, and then tried construct tours via highly parallelized beam search. Additionally, several algorithms belonging to above paradigm were further enhanced with OR based algorithms, thus also belonging to this paradigm. For example, the solution obtained by ML is post-optimized by sampling in (Bello et al. (017)) and (Kool et al. (019), or by 2-opt based local search (Deudon al. 2018). Overall, this hybrid paradigm performs statistically much better than the end-to-end MI. paradigm, showing the advantage of combining MI. with OR.
In addition to the works focused on the classic TSP, there are several ML based methods recently proposed for solving other related problems, such the decision TSP (Prates et al. 2019), the multiple TSP (Kaempfer & Wolf 2019), and the vehicle routing problem (Nazari et al. 2018), etc.
Finally, for an overall survey about machine learning for combinatorial optimization, please refer to Bengio et al. 2018) and (Guo et al. 2019).
METHOD
3.1
FRAMEWORK
Problem definition
Initialization
2-opt local search within small neighborhood (OR)
Sampling via MCTS within enlarged neighberhood (ME)
Terminate?
Yes
Solution
No
Jump to unexplored search space
Figure New paradigm for combining OR and ML to solve the TSP
The proposed new paradigm for combining OR and MI. to solve the TSP is outlined in Fig. I Specifically, the search process is considered as Markov Decision Process (MDP), which starts from an initial state ग, and iteratively applies an action a to reach a new state ". At first, the MDP explores within small neighborhood, and tries to improve the current state by applying 2-opt based local search. When no further improvement is possible within the small neighborhood, the MDP turns into enlarged neighborhood, which consists of large number of possible actions, being infeasible to enumerate one by one. To improve search efficiency, MCTS launched to iteratively sample number of promising actions and choose improving action to apply. When MCTS fails
3

---

Under review as a conference paper at ICLR 2020
to find improving action, the MDP jumps into unexplored search space, and launches round of 2-opt local search and MCTS again. This process is repeated until the termination condition met, then the best found state is returned as the final solution.
3.2 STATES AND ACTIONS
In our implementation, each state corresponds to complete TSP solution, i.c., permutation (TI, .T.....,Ty TT) of all the cities. Each action a is a transformation which converts given state to state πτ. Since each TSP solution consists of subset of edges, each action could be viewed as a k-opt (2 < k S n) transformation, which deletes k edges at first, and then adds different edges form new tour.
Obviously, each action can be represented as series of 2k sub-decisions (k edges to delete and edges to add). This representation method is straightforward, but seems a bit redundant, since the deleted edges and added edges are highly relevant, while arbitrarily deleting k edges and adding k edges may result an unfeasible solution. To overcome this drawback, we develop compact method to represent an action, which consists of only l sub-decisions, as exemplified in Fig. 2
(a) starting
(b) after deleting (3.4)
(c) after connecting to
5 6 6
(d) after deleting (7.6)
(c) after connecting to 7
(f) after deleting (2,3)
(g) after connecting 4
(h) state
Figure 2: The decision process of an example action
To determine an action, we first decide city aı and delete the edge between d1 and its previous city b. Without loss of generality, suppose = 4, then by = 3 and edge (3, 4) is deleted, resulting in a temporary status shown in sub-figure (b) (for the sake clarity, drawn as a line which starts from aj and ends 61). Furthermore, we decide city to connect city b, generally resulting in an unfeasible solution containing an inner cycle (unless 02 a1). For example, suppose 02 6 and connect it to city 3, the resulting temporary status is shown in sub-figure (c), where inner cycle occurs and the degree of city 02 increases to 3. To break inner cycle and reduce the degree a2 to the edge between city d2 and city b2 = 7 should be deleted, resulting in temporary status shown in sub-figure (d). This process is repeated, to get a series of cities dg and by 2 2). In this example, a3 = 3 and by 2, respectively corresponding to sub-figures (e) and (f). Once aj d1, the loop closes and reaches a new state (feasible TSP solution). For example, if let a2 = ai = and connect a, to by, the resulting new state is shown in sub-figure (g), which is redrawn cycle in sub-figure (h).
In Fig. 2 sub-figure (a) is the starting state π = (1, 2,,,4,5,6,77

---

Under review as a conference paper at ICLR 2020
Formally, an action can be represented as (a1, b1 ag2 .g....... 0g. bb, ak+1). where & is variable and the begin city must coincide with the final city, i.. as+1 = Q1. Each action corresponds to k-ppt transformation, which deletes & edges, i.c., (a,, 6,), S i i k. and adds k edges, i.e., (b;, 0++1), 1 S i S k. to reach new state. Notice that not all these elements are optional, since once a, is known, b; be uniquely determined without any optional choice. Therefore, determine action we should only decide series of k sub-decisions, i.c., the & cities a,, 1 S i I k. Intuitively, this compact representation method brings advantages two-folds: (1) fewer (only not 2k) sub- decisions need to be made; (2) the resulting states are necessarily feasible solutions.
Furthermore, if a++1 does not belong to the top 10 nearest neighbors of b;, edge (bs, a++1) is marked as an unpromising edge, and any action involving (b,, a++1) is marked as an unpromising action. All the unpromising actions are eliminated directly, to reduce the scale of search space.
Let L(π) denote the tour length corresponding to state π, then corresponding to each action (a1, bj, 02 bg...... 0gg by, ak++1) which converts π new state л², the difference A(T,, x²)
L(T²) - L(T) could be calculated as follows:
A(T, TT
Σ dbya.+1
daybe
(1)
If A x²) < O, πT is better (with shorter tour length) than π.
3.3 STATE INITIALIZATION
For state initialization, we choose a simple constructive procedure which starts from an arbitrarily chosen begin city T1, and iteratively selects a city n; S S among the candidate (unvisited) cities (added to the end of the partial tour), until forming complete tour which serves as the starting state. More precisely, there are m 1 candidate cities the ith iteration, each candidate city is chosen with probability L. Using this method, each possible state chosen as the starting state with an equal probability.
(T ....... x,)
3.4 2-OPT LOCAL SEARCH WITHIN SMALL NEIGHBORHOOD
To maintain the generalization ability of our approach, we avoid to use complex OR techniques, such as the a-nearness criterion for selecting candidate edges (Helsgaun) 2000) and the partition and merge method for tackling large TSP instances (Tallard & Helsgaun, 2019). which have proven be highly effective on the TSP, but heavily depend on expert knowledge.
Instead, we choose a straightforward method to search within a small neighborhood. More precisely, the method examines one by one the promising actions with A 2, and iteratively applies the first- met improving action which leads to better state, until no improving action with k = 2 is found. This method is equivalent the well-known 2-opt based local search procedure, which able to efficiently and robustly converge local optimal state.
3.5 TARGETED SAMPLING OF ENLARGED NEIGHBORHOOD VIA MCTS
Yes
Initialization
Simulation
Selection
Terminate?
Solution
No
Back propagation
Figure 3: Procedure the Monte Carlo tree search
5

---

Under review as a conference paper at ICLR 2020
Once no improving action is found within the small neighborhood. close the basic 2-opt local search, and switch to an enlarged neighborhood which consists the actions with & This method is generalization of the variable neighborhood search method (Mladenovié & Hansen 1997). which has been successfully applied to many combinatorial optimization problems.
Unfortunately, there are generally huge number of actions within the enlarged neighborhood (even after eliminating the unpromising ones), being impossible to enumerate them one by one. Therefore, choose to sample subset of promising actions (guided by RL) and iteratively select an action to apply, to reach a new state.
Following this idea, we choose the MCTS
learning framework. Inspired by the works in (Coulom 2006), (Browne et al. 2012), (Silver et al., (016) and (Silver et al., (017).. our MCTS procedure (outlined in Fig. 3 consists of four steps, i.c., (1) Initialization, (2) Simulation, (3)
Selection, and (4) paopappoo,,,tton, which are respectively designed as follows.
Initialization:
symmetric matrices, i.e., a weight matrix W whose element We (all initialized to 1) controls the probability of choosing city j after city i, and an access matrix Q whose element Qıy (all initialized to 0) records the times that edge (i,j) is chosen during sim- ulations. Additionally, variable M (initialized to 0) is used to record the total number of actions already simulated. Notice that this initialization step should be executed only once at the beginning of the whole process of MDP.
We define two
Simulation: Given a state т, we use the simulation process to probabilistically generate number of actions. As explained in Section 3.2 each action is represented
(a1, bj, 02 by....... ag. by, ag+1). containing series of sub-decisions a; 1 < S (I: is also a variable, and ax+1
a1), while b, could be determined uniquely once a, is known. Once b; is determined, for each edge (b;, * bú, we use the following formula to estimate its potential Zo (the higher the value of Zbuj. the larger the opportunity of edge (b;,j) be chosen):
In (M 1) Whi + +ay Q +1
Zo, =
Po.
Where Do. Eye,, Way
denotes the averaged Woy value of all the edges relative city b; In emphasizes the importance of the edges with high Why values (to Th
Lime,
What
this formula, the left part
In (M prefers the rarely examined Qbuj +1
enhance the intensification feature), while the right part
edges (to enhance the diversification feature). a is a parameter used to achieve balance between intensification and diversification, and the term "+1" is used to avoid a minus numerator or zero denominator.
To make the sub-decisions sequently, we at first choose aj randomly, and determine b subsequently. Recursively, once a and b; are known, 0;+1 is decided as follows: (1) if closing the loop (connecting aj to b,) would lead to improving action, or 2 10, let 0,+1 = 01 (2) otherwise, consider the top 10-nearest neighbors of b, with Zo, 2 as candidate cities, forming a set X (excluding a and the city already connected to b;). Then, among each city j is selected as 0;41 with probability Pj- which is determined as follows:
Zoot
Pj Σiex Zo,i
(3)
Once a;+1 = 41, we close the loop to obtain an action.
Similarly, more actions generated (forming sampling pool), until meeting an improving action which leads to a better state, or the number of actions reaches its upper bound (controlled by a parameter H).
Selection: During above simulation process, an improving action is met. it selected and applied to the current state π, get new state new Otherwise, if no such action exists in the sampling

---

Under review as a conference paper at ICLR 2020
pool, it seems difficult gain further improvement within the current search area. At this time, the MDP jumps to a random state (using the method described in Section 3.3 which serves as a new starting state.
Back- Back-propaggtion The value of M as well as the elements of matrices W and Q are updat- ed by back propagation follows. At first, whenever action is examined, M is increased by Then, for each edge (b,, (;1) which appears an examined action, let Qiaa- in- crease by Finally, whenever a state क converted better state nee by applying action = (al, bi, 02, b2,...y ... Uk, bb, ax+1), for each edge (b;, (i+1),1 S S k. let:
((TT)
L new L(T))
-1]
Wora0 < Wbra +
exp
(4)
a parameter used to control the increasing rate Whaah::- Notice that we update Whaaaa only when meeting better state, since want to avoid wrong estimations (even in bad action which leads to a worse state, there may exist some good edges (b,, a++1)). With this back- propagation process, the weight of the good edges would be increased enhance opportunity of being selected, thus the sampling process would be more and more targeted.
Where 3
W and Q symmetric matrices, thus let W 1b W6, and Qe4t = Qbeait always.
3.6 TERMINATION CONDITION
The MCTS iterates through the simulation, selection and back sock-propagation steps, until no improving action exists among the sampling pool. Then, the MDP jumps to a new state, and launches a new round of 2-opt local search and MCTS again. This process repeated, until the allowed time (controlled by parameter 7) has been elapsed. Then, the best found state is returned as the final solution.
EXPERIMENTS
To evaluate the performance of our MCTS algorithm, we program it in C language and carry out experiments on large number of public TSP instances. Notice that the reference algorithms are executed on different platforms (detailed below), being extremely difficult to fairly compare the run times. Therefore, we mainly make comparisons in terms of solution quality (achieved within reasonable runtime), and just list the run-times roughly evaluate the efficiency of each algorithm.
4.1
DATA SETS
Currently there two data sets widely used by the existing learning based TSP algorithms, i.e., (1) Set which is divided into three subsets, each containing 10,000 automatically generated Eu-llucidean TSP instances, respectively with 20, 50, 100. (2) Set 2 which contains 38 instances (with 51 S n & 318) extracted from the famous TSPLIB library (Reinelt 1991). We also these data sets benchmarks evaluate our MCTS algorithm.
4.2 PARAMETERS
As described in Section MCTS relies on four hyper parameters (a, H and T). We choose 10n (n is the number of cities) as the default settings of the first three
1, 3 = 10, parameters. For parameter T used control the termination condition, we for each instance of set 1, and set T = seconds for each instance of set 2, to ensure that the total time elapsed by MCTS remains reasonable w.r.t. the existing learning based algorithms.
75n milliseconds
"Code and http:///aaa...ooo....ccooooddass
https: https://wwwproxx.ink htt.::/www..aoooooooooooooooooon

---

Under review as a conference paper at ICLR 2020
4.3 RESULTS ON DATA SET 1
Trresentt the results obtained by MCTS data set 1, with respect the existing non-learned and learning-base based algorithms. In the table, each line corresponds to an algorithm. Respectively, the first nine lines non-learned algorithms, among which Concorde (Applegate al. 2006) and Gurobi (Gurobi Optimization] 2015) are two exact solvers, LKH3 (Helsgaun) (017) is the currently best heuristic, and OR tools are optimization tools released by Google company (Google 2016). The following six lines are end-to-end ML models (the MCTS algorithm in (Shimomura & Takashima 2016) did not provide detailed results, thus being omitted), and the final eight lines are hybrid algo- rithms which use OR method after ML for post-optimization. For the columns, column 1 indicates the methods, while column 2 indicates the type of each algorithm (explained the bottom of the table), columns 3-5 respectively give the average tour length, average optimality gap in percentage w.r.t. Concorde, and the total clock time used by each algorithm on all the 10,000 instances with 20. Similarly, columns 6-8, 9-11 respectively give the same information on the 10,000 instances with n = 50 and n = 100. All the results except ours are directly taken from table of (Joshi et al.) 2019) (the order of the algorithms is slightly changed), while unavailable items are marked "'".
Notice that in the latest learning based algorithms (Kool et al. 2019) and (Joshi et al. 2019), the experiments were carried out either
single GPU (Nvidia 1080T)) 32 instances in parallel on a 32 virtual CPU system (2 x Xeon ES E5-2630), and the run-time was recorded as the wall clock time used solve the 10,000 test instances. Similarly, we also run 32 instances parallel 32 virtual CPU system (2 x Intel Xeon Silver 41 10 2. processor, each with eight cores), and report the wall clock time used to solve the 10,000 test instances.
Table I: Performance of our MCTS algorithm on data set 1, compared to non-learned algorithms (first nine lines), end-to-end ML models (following six lines), and hybrid algorithms which use OR after ML (final eight lines). The optimality gap is computed w.r.t Concorde (best exact solver).
TSP20
TSP50
TSP100
Method
Type
Tour len.
Opt. Gap.
Time
Tour Len.
Opt. Gap.
Time
Tour Les.
Opt, Gap.
Time
Concoode
Applecate et el.
2006
Buat Solver
3.84
0.00%
5.70
0.00%
2m
7.76
0.00%
3m
Gurobi Guroty Up Upzenzztoon
2
Baxt Solver
3.84
0.00%
7s
5.70
0.00%
2m
1.76
0.00%%
17m
LKH3
Hesgain
3.84
0.00%
5.70
0.00%
5m
0.00%
Neuess Iisrroon
G.G
4.33
12.91%
6.75
19.03%
21.82%
Random Insection
H
4.00
4.36%
Os
6.13
7.65%
8.52
9.69%
3s
Fartest Inseriion
H.G
3.93
2.36%
Is
6.01
5,538
2
8.35
7,59%
7s
Newest Neighbor
H.G
4.50
17.22%
Os
7.00
22.9%%
9.68
24.73%
OR Tools
Google 2016
H.S
0,37%
5.80
2.0%
Chrl.
2017
H. 20PT
3,65
0,37%
5.79
1.68%
PiNNet
Vinvals et 2015
SL, G
3.58
1.15%
7.65
34,48%
PuNet
Hojo et 2017
RL. G
3.89
1.4%
5.95
4,46%
8.30
6.90%
S2V-DONN
Khail cinl. 2017
G
3.50
1.42%
5.99
5.16%
8.31
7.03%
GAT
Deudoz
G
3,86
0,66%
5.92
3.98%
8.1%
8m
GAT
Kooi al 20199
RL. G
3.65
0.34%
Os
5.80
1.76%
8.12
4.53%
6s
GCN
Josin el 20 2mn9
SI, G
3,96
0.60%
6s
5.87
3
53s
8.41
R388%
6m
GNN
Nowal c..l
2011
SL, BS
3.93
2.46%
PinNer
2017
RL,
5.75
0.95%
5003
GAT
O2ugon
RL,
3.84
0,11%
5.77
1.28%
17m
12.70%
GAT
Deudon et 2013
RL, G. 2OPT
3.65
0.42%
4m
5.85
2.77%
26m
8.17
5.21%
3b.
GAT
Dzaioz ct 2013
RL, S. 20PT
3.84
0.09%
6m
5.75
1.00%
32m
8.12
4.64%
Sh
GAT
K0ol et 3319
RL,
3.84
0.08%
5.73
0.52%
24m
2.26%%
1h
GCN
Joslu
2009
BS
3.84
0.10%
5.71
0.26%
2m
2.11%
GCN
ef
SL, BS*
3.84
0,00%
12tz
5.70
0.01%
18m
7.87
1,39%
40n
MCTS
loues)
RL, 20PT
3,330
4.0075%
3m
5,6066
4.0212%
20m
7,7631
40.078%%
40m
H: Heurieic, SI.; Supervised I Learning. RL: Reinfonmeent Leorning, G: Gredyy S. Sampling. search, RS+: BS and shonest tour hearistic, 20PT. 2-opt local seanch.
As shown in [able[] the exact solvers and LKH3 obtain good results on all the test instances, while the remaining six non-learned algorithms perform overall poorly. Among the learning based al- gorithms, in terms of solution quality the hybrid algorithms which combines ML and OR perform clearly much better than the end-to-end ML models, although much more computational times required. Finally, compared to these existing methods, our MCTS algorithm performs quite well, which succeeds in matching improving the best known solutions (reported by Concorde) on most
8

---

Under review as a conference paper at ICLR 2020
of these instances, corresponding to average gap of -0.0075%. -0.0212%, -0.0178 % respec- tively on the three subsets with n = 20, 50, 100. The computation times elapsed by MCTS remains reasonable (40 minutes for the 10,000 instances with 100), close to the latest (currently best) learning based algorithm (Joshi et al. 2019).
4.4 RESULTS ON DATA SET 2
This set contains 38 instances (51 S 318) extracted from the TSPLIB. For each of these in- stances, we list in Table the optimal result (reported by Concorde within hour for each instance), the results reported by S2V-DON (Khalil et al. 2017) and our MCTS algorithm (indicated in bold if reaching optimality). Notice that S2V-DQN did not clearly report the computational time, while n seconds allowed by our MCTS solve each instance with cities (the 38 instances are executed sequentially, occupying a core of an Intel Xcon Silver 41 10 2. GHZ processor).
As shown in the table, S2V-DQN reaches optimality on only one instance (berlin52), corresponding to large average gap (w.rtt the optimal solutions) of 4.75%. For comparison, our MCTS succeeds in matching the optimal solutions on 28 instances, corresponding to a much smaller average gap (0.21 %). Furthermore, MCTS dominates S2V-DQN on all these instances only except two instances pr226 (worse than S2V-DQN) and berlin52 (with equal results), clearly demonstrating its superiority over S2V-DQN.
Table 2: Performance of MCTS on data set 2 compared to S2V-DQN (Khalil et al.
2017
Instance
OPT
S2V-DON
MCTS
Instance
OPT
S2V-DQN
MCTS
426
426
berlin52
7542
7542
7542
S170
675
696
675
eil76
538
564
538
pr76
108159
ra199
1211
1211
kroA100
21282
21897
21282
kroB 100
22141
22692
22141
kroC100
20749
21074
20749
kroD100
21294
22102
21294
kroE100
22068
22913
22068
rd100
7910
8159
7910
cil101
629
659
629
lin105
14379
15023
14379
pr107
44303
pr124
bier127
118282
121576
118282
ch1.30
6110
6270
6110
pr136
prl44
ch150
6528
6985
6528
kroA150
26524
27888
26524
XroB150
26130
27209
26130
pr152
73682
75283
73682
u159
42080
45433
42080
rai195
2323
2581
2324
d198
15780
16453
15785
km>2000
29368
30965
29368
kroB200
ls225
126643
126643
ts2225
3916
4154
7926
pr226
80369
81873
83467
gi1262
2378
2537
pr264
49135
52364
49135
a280
2579
2867
2579
pr299
48191
51895
48195
lin318
42029
45375
42314
linhp318
41345
45444
42305
The average gap of S2V-DON vs. OPT 4.75%, while the average gap of MCTS vs. OPT 0.21%.
Overall, we think the experimental results on above two data sets clearly show the potential of our MCTS on the TSP.
CONCLUSION
This paper newly develops novel flexible paradigm for solving TSP, which combines OR and ML in a variable neighborhood search strategy, and achieves highly competitive performance with respect the existing learning based TSP algorithms. However, how to combine ML and OR reasonably is still an open question, which deserves continuous investigations. In the future, we would try more new paradigms better answer this question, and extend the work to other combinatorial optimization problems.
*On many instances, the best known solutions reported by Concorde are not strictly optimal (confirmed Joshi et al. 2019), possibly due to round-off reasons), which could be slightly improved (< 10-2) by our MCTS algorithm. On the 10,000 instances with 20, 50, 100, MCTS respectively improves (with different permutations of the cities) 1094, 3682, 6404 and misses O, O, 1273 hest known solutions, while matching the hest known solutions on all the remaining instances.

---

Under review as a conference paper at ICLR 2020
REFERENCES
David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. 2006.
Concorde tsp solver.
David L Applegate, Robert E Bixby, Vašck Chvátal, William Cook, Daniel G Espinoza, Marcos Goycoolea, and Keld Helsgaun. Certification of an optimal tsp tour through 85,900 cities. Oper- ations Research Letters, 37(1): 1-115, 2009.
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinato- rial optimization with reinforcement learning. In Proceeding of the International Conference on Learning Representations (ICLR), 2017.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimiza- tion: methodological tour d' d'horizon. arXiv preprint arXiv:/8/1.0611 1.06/88, 2018.
Cameron B Browne, Edward Powley, Daniel Whitchouse, Simon M Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in games, 4(1):1-43) 2012.
Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In International conference on computers and games, pp. 72-83. Springer, 2006.
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the tsp by policy gradient. In International Conference the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 170-181. Springer, 2018
Patrick Emami and Sanjay Ranka. Learning permutations with sinkhorn policy gradient. arXiv preprint arXiv:1805.0700 2018
Google. Or-tools, google optimization tools. http://ddeeeepppssoo...ccoooooot 2016.
Tiande Guo, Congying Han, Sigi Tang, and Man Ding. Solving combinatorial problems with ma- chine learning methods. In Nonlinear Combinatorial Optimization, pp. 207-229, Springer, 2019.
Incorporate Gurobi Optimization. Gurobi optimizer reference manual. URI. http://www.gurmbb.com 2015.
Keld Helsgaun. An effective implementation of the lin kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1):106-1 -100, 2000.
Keld Helsgaun. An extension of the fin-kernghaanhhelseee tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 2017.
John J Hopfield and David W Tank. Neural computation of decisions in optimization problems. Biological cybernetics, 52(3):441-52, 1985.
Chaitanya K Joshi. Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network
technique for the travelling salesman problem. arXiv preprint SttV:::900001227.. 2019.
Yoav Kaempfer and Lior Wolf. Learning the multiple traveling salesmen problem with permutation invariant pooling networks. In Proceeding of the International Conference on Learning Repre- sentations (ICLR), 2019.
Elias Khalil, Hanjun Dai, Yuyu Zhang. Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. In Advances in Neural Information Processing Systems (NeurIP. S), pp. 6348-6358. 2017.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference Learning Representations (ICLR), 2019.
10

---

Under review as a conference paper at ICLR 2020
Nenad Mladenović and Pierre Hansen. Variable neighborhood search. Computers & operations research,
1997.
Mohammadreza Nazari, Afshin Oroojlooy. Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems (NeurIPS), pp. 9839-9849, 2018.
Alex Nowak, Soledad Villar, Afonso S Bandeira, and Joan Bruna. A note on learning algorithms for quadratic assignment with graph neural networks. Proceeding of the 34th International Conference Machine Learning (ICML), volume 1050, pp. 22, 2017.
Marcelo Prates, Pedro HC Avelar, Henrique Lemos, Luis C Lamb, and Moshe Y Vardi. Learning to solve np-complete problems: A graph neural network for decision tsp. In Proceedings of the AAAI Conference Artificial Intelligence (AAAI), volume 33, pp. 4731 2019.
César Rego, Dorabela Gamboa, Fred Glover, and Colin Osterman. Traveling salesman problem heuristics: Leading methods, implementations and latest advances. European Journal of Opera- tional Research, 211 2011.
Gerhard Reinelt. Tspliba traveling salesman problem library. ORSA journal on computing, 3(4): 376-384, 1991.
Masato Shimomura and Yasuhiro Takashima. Application of monte-carlo tree search to traveling- salesman problem. In The 20th Workshop on Synthesis And System Integration of Mixed Informa- fion technologies (SASIMI), pp. 352-356, 2016
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game go with deep neural networks and tree search. Nature, 529(7587):484, 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):354, 2017.
Kate A Smith. Neural networks for combinatorial optimization: a review of more than a decade of research. INFORMS Journal on Computing, 11(1):15-34, 1999.
Éric D Taillard and Keld Helsgaun. Popmusic for the travelling salesman problem. European Journal of Operational Research, 272(2):420-429, 2019.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in Neural
Information Processing Systems (NeurIPS), pp. 2692-2700, 2015.


Reviews:
[{"review_id": "r1ezQrs3tB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a machine-learning based heuristic for solving traveling\nsalesman problems. In particular, MCTS is used to explore a large neighbourhood.\nThe authors present their approach and evaluate it empirically.\n\nThe presented approach is interesting; a few details could be described in more\ndetail and motivated better (for example how the particular functional form for\nestimating the potential Z of an edge was chosen). but in general the paper is\nwell-written.\n\nThe main part where the paper falls short is the experimental evaluation. The\nauthors state that the reference algorithms were executed on different\nplatforms, even though at least some of them are publicly available and the\nauthors could have run them themselves. In their own experimental setup, the\nauthors overload the machines by solving instances on each hyper-threaded\nlogical core instead of the physical cores for no apparent reason. Running on\nlogical cores like this leads to significantly longer runtimes. This\nexperimental setup is changed for instance set 2 for no apparent reason.\n\nThe authors claim to improve on the optimal solution that concorde finds,\nconfirmed by a non-peer-reviewed paper, without providing a justification -- if\nthis is due to rounding errors, are the found tours the same and just the length\ncomputation is flawed? Or are the tours different?\n\nTables 1 and 2 present results in completely different formats. This makes it\nunnecessarily hard to compare results. In particular, Table 2 presents no run\ntimes.\n\nFinally, the instances used to evaluate the approach seem relatively easy.\nTSPlib contains many more instances that are more challenging to solve, with\nhundreds to thousands of cities. Even on the relatively small instances, the\npresented approach is often an order of magnitude slower than the exact solver\nconcorde -- why would I want to use the presented approach in a practical\nsetting?\n\nIn summary, I feel that the paper cannot be accepted in its current form.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SylAGeiatB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an algorithm for the Travelling Salesman Problem that starts with a random tour and iteratively improves it using 2-opt local search, followed by Monte Carlo Tree Search with k-opt moves to search a larger neighborhood of solutions. Results show that the algorithm matches the optimal objective value on a dataset of 2D Euclidean TSP instances with 20, 50, and 100 cities, and achieves better objective value than S2V DQN on a subset of instances from TSPLIB with 50 to 318 cities. It is interesting that the algorithm is fairly simple (apart from the definition of the local moves) and still able to achieve competitive objective values on small instances.\n\nThe rating is a weak reject for the following reasons:\n1. Domain knowledge: The proposed algorithm has significant domain knowledge about TSP hand-coded into it via the choice of 2-opt local search as well as the k-opt moves with top-10 nearest neighbor filtering used in MCTS. These types of moves are same/similar to the expert-designed ones used in state-of-the-art local search algorithms like LKH. This can give the proposed algorithm a significant advantage over S2V-DQN which does not have such built-in knowledge. So the comparison to S2V-DQN is unfair and improved results may not be due to any differences in the learning approaches at all. Perhaps a more generic definition of local moves that is not so TSP-specific would be a fairer comparison. This issue is particularly important because the definition of “local moves” appropriate for a problem domain is one of the main challenges in applying local search successfully. Bypassing that challenge can simplify the problem.\n\n2. Baselines: Better comparisons to baselines are needed in Table 2. S2V-DQN was published two years ago, and since then many other learning-based have been proposed (which are referenced in the paper), but they are not included in Table 2. It would also be good to discuss non-learning local search algorithms that use same/similar local moves as the proposed algorithm and how they perform.\n\n3. Scalability to large instances: TSP experts consider problems with hundreds of cities as practically “solved” by the current state-of-the-art solvers like Concorde and LKH, and it is not at all clear what benefit learning can provide on such small instances. Much larger instances (e.g., 10^4-10^6 cities) would have to be considered for improvements over the state-of-the-art to become plausible with learning. So if the goal is to improve on the state-of-the-art with learning (even if it is a long-term goal), then it is important to consider whether the proposed approach has a plausible path for scaling up to such sizes. But like most papers on learning-for-TSP, this paper does not consider scalability. \n\nMisc comments:\nIt would be useful to include the exact running times of Concorde in Table 2. The results given are “reported by Concorde within 1 hour for each instance”, but it would be good to know what the actual running time is.\nTypo: “sub-decisions sequently”\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "S1x3aFAFuS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new RL-based algorithm for solving the traveling salesman problem (TSP). Its main component is the combination of OR-based 2-opt search and learning-based k-opt search. Monte Carlo tress search is employed to train the learning-based k-opt search. The experimental result suggests state-of-the-art performance over existing RL-based solvers. \n\nMy main criticism is about the positioning of the paper in the literature. This algorithm is more of an \"online\" RL algorithm with learning done for each TSP instance separately, while the compared \"offline\" RL algorithms perform learning over the TSP algorithm (and training dataset). Regarding this matter, I failed to understand the advantage or promise of the proposed algorithm over the existing solvers such as Concorde. The motivation in the paper states that existing OR algorithms are \"very complicated and consist of many hand-crafted rules and heavily rely on expert knowledge, thus being difficult to generalize to other combinatorial optimization problems\", but this algorithm seems to suffer the same problems. In particular, one could even assert that the proposed algorithm is an instance of the Tabu search method [1], which is based on keeping a record of actions taken and penalizing to revisit it. \n\nFurthermore, I think the experiment lacks some detail regarding the complexity of the algorithm. The comparison of the proposed algorithm to the existing RL-based algorithms is slightly unfair, given that the proposed algorithm is implemented in C and others are implemented in Python (except S2V-DQN). For instance, when MCTS and the method of (Joshi et al., 2019) both take 40 minutes on the TSP-100 dataset, it is likely that MCTS is slower when implemented in Python. I would suggest the authors to avoid misleading the readers by including this fact in the paper. I also suggest providing the number of iterations it took to achieve the reported results since one could compare it to other local search methods. Furthermore, the experiments seem to lack the details on the number and type of GPUs used for obtaining the reported results.  \n\n[1] Zachariasen and Dam, Tabu Search on the Geometric Traveling Salesman Problem, Meta-Heuristics. Springer 1966\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper contributes to the recently emerging literature about applying reinforcement learning methods to combinatorial optimization problems.
The authors consider TSPs and propose a search method that interleaves greedy local search with Monte Carlo Tree Search (MCTS).
This approach does not contain learned function approximation for transferring knowledge across problem instances, which is usually considered the main motivation for applying RL to comb opt problems.

The reviewers state that, although the approach is a relatively straight-forward combination of two existing methods, it is in principle somewhat interesting. 
However, the experiments indicate a large gap to SOTA solvers for TSPs. 
No rebuttal was submitted.

In absence of both SOTA results and methodological novelty, as assessed by the reviewers and my owm reading, I recommend to reject the paper in its current form.
Decision: Reject