Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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.
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_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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
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. 

The 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. 

Even 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. 

These 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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.

From 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.

From 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.
main_review: # 1. Strengths

1.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.

1.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.

1.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).

---

# 2. Weaknesses & Things to be addressed

## 2.1. On evaluation setup:
- 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].
- 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.
- 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?
- 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.)  
- 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.

## 2.2. On missing latest related work and comparisons:
- 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.
- 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.

## 2.3. Missing generalization to other problems
An 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.) 

---

# 3. Other minor comments and suggestions

## 3.1. On message-passing over line graphs vs. message-passing over nodes and edge features: 
- 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.  
- 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.

## 3.2. On motivation for this work: 
- 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.
- 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.
- 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?)

## 3.3. On scalability of dataset generation: 
It 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)?

## 3.4. On style of reporting empirical results: 
I 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.

---

# References

[1] Florian Arnold and Kenneth Sorensen. Knowledge-guided local search for the vehicle routing problem. Computers & Operations Research, 105:32–46, 2019.

[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.

[3] Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475, 2018.

[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.

[5] Wouter Kool, Herke van Hoof, Joaquim Gromicho, Max Welling. Deep Policy Dynamic Programming for Vehicle Routing Problems. arXiv preprint, 2021.

[6] Zhang-Hua Fu, Kai-Bin Qiu, Hongyuan Zha. Generalize a small pretrained model to arbitrarily large tsp instances. AAAI 2021. 

[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.

[8] Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, Thomas Laurent. Learning TSP Requires Rethinking Generalization. CP 2021.

[9] Luca Accorsi, Andrea Lodi, Daniele Vigo. Guidelines for the Computational Testing of Machine Learning approaches to Vehicle Routing Problems. arXiv preprint, 2021.

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.

---

# Update after rebuttal

I 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).

I 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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
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.

Pros: 
 
1. 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.
 
2. 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. 

Cons: 
 
1.	The 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.

2.	The 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?


summary_of_the_review: The contribution of the paper is significant and somewhat new with insights into the TSP problem by GNN.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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. 

main_review: Pros:

1. The paper is well-written and easy to follow. 

2. Hybridizing machine learning with local search is an interesting approach.

3. The experimental results show that the proposed algorithm outperforms other recently published learning-based algorithms, which is nice.  
 

Cons: 

1. 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. 
 
2. 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.
 
3. 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.  

4. 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.

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.
review_title: null

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)