Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The current paper proposes a new algorithm that combines deep learning with the heuristic solver for solving various vehicle routing problems, TSP, CVRP, PDP, CVRPTW. The method proposes a Sparse Graph Network (SGN) that produces edge scores and node penalties, which are then used to the edge candidate set and transformed edge distance. Once the edge candidate set and the transformed edge distances are computed, a conventional /lambda-opt algorithm is repeatedly used to produce the final best routing solution. The proposed sore functions are trained with small-sized problems sampled uniformly using supervised learning and unsupervised learning. Finally, the trained model is used to solve the test problems whose node distribution is different and whose node number is large. The proposed algorithm consistently outperforms its baseline, LKH, and VSR-LKH. 
main_review: <Originality>
Combining a well-known and effective search heuristic with a learning-based score model sounds reasonable and effective in solving the target problem. In solving vehicle routing problems, various approaches devise improvement heuristics. While comparing with these improvement heuristics, please mention the unique novelty of the proposed method.

<Quality>
The architecture of SGN is pretty simple. It would be good author justify the design choice of the architecture and the hyperparameters used. 

Q1. What is the rationale behind choosing the proper number of $\gamma$? 

Q2. Why embedding layer uses skip connection? 

Q3. How to determine the number of layers? When the size of the graph changes, the same number of layers is used? The number of layers can be possibly jointly determined with the sparsity parameter $\gamma$?

The SGN is trained with both supervised loss and unsupervised loss. I have several concerns about this approach:

Q4. The biggest concern is that the method requires the optimal solution or a good solution to produce a good supervise label. What are the benefits of using the imitation learning approach comparing to reinforcement learning approach? It would be nice to compare the pros and cons and justify your selection. 

Q5. What is the rationale behind using the unsupervised loss? How to compute $d_i(\pi)$ and is ti differentiable? And why this factor should close to 2? 

Q6. Can you train both edge score function and node penalty function simultaneously using reinforcement learning without accessing the optimum solution? What is more beneficial for generalizing over different node sizes and node distribution between imitation learning and reinforcement learning?

<Clarity>
The paper is well written and well organized.

<Significance >
The current paper replaces the existing empirical procedure for constructing edge candidate sets with a neural network-based edge candidate selection procedure. The proposed sparse graph network is a simple variant of a graph neural network with limited edge connectivity. I believe replacing a rule-based heuristic module with a learning-based module can naturally result in performance improvement. The paper does not propose a different way of problem-solving but proposes a straightforward extension to the original approach; the technical significance and novelty are limited. 

In addition, the proposed method does not effectively generalize over the new test problems with different node distribution and different node numbers. The proposed method seems to work better than other baselines but often fails to solve the problems. In addition, it is hard to see that the method is completely transferable in that it requires fine-tuning.

limitations_and_societal_impact: The author comments that the proposed method generalizes well to large sizes and different distributions of nodes and does not generalize well to other distributions of demands and time windows without further training.

To achieve the generalization capability of the trained model over other aspects, the specially designed architecture or specially designed training scheme are generally required. The current study does not explicitly mentions such additional efforts but evaluates their performance. It would be good if the authors discuss the indented design choice to achieve what desirable performance and validate that argument through several ablation studies.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a neural version of the classic LKH algorithm, where the subgradient optimization of LKH is replaced by a sparse GNN that predicts edge candidates and node penalties that can directly be used by the LKH search algorithm. The edge candidate predictions are learned supervised from optimal solutions whereas the penalties are learned 'unsupervised' to push the node degrees of the 1-tree induced by the penalties towards 2 (I consider this is more like RL where the deviation from node degree 2 determines the reward). After training, the NeuroLKH algorithm gives better results than the standard LKH algorithm given equal time, for the travelling salesman problem (TSP) and different vehicle routing problems (VRPs).

As the node penalties are only used for TSP, the major contribution seems to show the empirical benefit of the edge candidate predictions. While this is not a new idea in itself, the combination with LKH is and as the empirical results are very promising, I think this paper makes valuable progress and therefore should be accepted.
main_review: **Originality**
On one hand, this paper presents a nice and simple idea of taking the subgradient objective for LKH but amortize its optimization over a set of instances to predict the node penalties for new instances without needing the subgradient optimization. On the other hand, the idea of learning to predict an edge candidate set is closely related to the cited works [19,21] and the differences are merely in architecture (most notably using a sparse network for increased scalability), so this in itself is not very novel. The combination with LKH, while relatively straightforward, has not been done before as far as I know.

**Quality**
The paper is technically of high quality. The claims are supported by a large number of experiments and ablations on different datasets, instance distributions and problem sizes. Care has been taken to present fair comparison by forcing running times equal, and helpful ablations are included in the appendix. My major concern is that the learned node penalties are only used with TSP, for which the practical differences in performance seem small. For CVRP and TSPTW, the difference with LKH and other baselines is much more convincing, but this seems only result of the edge selection by the network. Therefore I consider the main contribution to show the strong empirical performance of using a carefully implemented neural network for edge selection in combination with an existing heuristic (LKH).

**Clarity**
Overall I found this paper very clear. Whereas a lot of space is used for the extensive empirical evaluation, I find most of the important details very clear, without going more in depth than necessary. The background on the LKH algorithm is very helpful and Figure 1 is very clear in pointing out the differences and similarities between LKH and NeuroLKH. I do have some questions about the unsupervised training and I think some of the mathematical notation can be improved (see below).

**Significance**
This paper shows promising results on relatively large instances for different problems using a relatively simple methodology, namely the selection of edges by a graph neural network (and the prediction of node penalties used to change the edge cost for TSP), which can then be used by LKH, a relatively general solver for VRP problems. Whereas the ideas are quite simple, I consider it valuable to demonstrate the empirical performance of this methodology, which encourages further exploration on larger or other problems, as well as combination with other, more powerful solvers than LKH (which do exist and could/should be mentioned in the paper, see e.g. Hybrid Genetic Search for CVRP, Vidal 2020).

**Minor comments**
- I find the equations (1), (2) a bit confusing. I think attn_ij^l is a vector which may be helpful to mention explicitly (and as such exp(.) is also element wise). Also, it may be worth to mention the dimension over which BatchNorm operates / that it is not an element wise function as in the equations.
- Also the notation (i,m) in E* is confusing since it looks as if i is a summation index while it is actually fixed. I suggest introducing N(i) as neighbours of i and sum over m in N(i).
- I think some more explanation could be helpful for the loss in eq. (8). I understand now that it is correct but I was a bit surprised at first not to see absolute signs or a squared difference (as in a MSE loss).
- L213, it would be helpful to explain/remind why the candidate sets are of much better quality than LKH (because they are trained on 'optimal' solutions, which I missed the first time reading).

**Questions**
- Why do you consider the attention 'cheap' (L160)? I think it is actually more expensive as it computes a softmax per individual feature.
- How does the unsupervised learning of the penalties work exactly? Does the model predict penalties, then find a minimum 1-tree, then use this for the loss? How are min-1-trees found for a batch of instances? What is the batch size used? This sounds very costly. Also, I would consider this more like a reinforcement learning problem then where the action is deciding the penalties.
- Do I understand correctly that starting from a sparse graph, some edges can never be in a solution? How does this affect solution quality? Especially for large scale VRPTW, I can imagine the optimal solution would not use the gamma = 20 shortest outgoing edges?
- How does C (eq. 6) relate to the scale of the coordinates / size of the problem instance? This seems important as the penalty and thus C is actually in distance units.
- Why can't node penalties be used with CVRP? When you fix the penalty for the depot to 0 (as number of visits to the depot may vary) I do not immediately see a problem?
- The penalties affect the quality of the alpha measure, but do I understand correctly that this is not used in NeuroLKH as the edge set is predicted directly? So the penalties are only used to change the edge distances used in the search?
limitations_and_societal_impact: The major limitation is the dependence on the actual distribution of the instances and is discussed in the discussion. While not discussed, I do not see any direct negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a machine learning approach to enhance the performance of a traditional heuristic LKH to solve routing problems. Specifically, a Sparse Graph Network is trained to select candidate edges for LKH to refine solutions. The experiments confirm that the proposed method can improve the performance of the original LKH and the VSR-LKH (based on RL) in general. 
main_review: This paper combines the merits of both ML and traditional optimization techniques to solve large and hard routing problems. The approach sounds reasonable and appealing. The proposed method is well described, and the experiment is extensive.

1. For the Sparse Graph Network to work, the original TSP instances need to be pre-processed, i.e., only keeping \gamma shortest edges for each node and removing others. I guess the parameter \gamma has a large impact on the performance of the model. Why \gamma is set to 20 in the experiments, and what is the impact if changing \gamma to a different value?

2. Following the previous comment, sparsifying TSP graphs based on edge distance might lead to a sub-optimal solution in the first place, as mentioned by the authors that a certain amount of edges in the optimal tour were removed in pre-processing. Techniques [1,2] that sparsify TSP graphs based on machine learning might work better here. 

    [1] Sun, Yuan, et al. "Generalization of machine learning for problem reduction: a case study on travelling salesman problems." OR Spectrum (2020): 1-27.

    [2] Fitzpatrick, James, Deepak Ajwani, and Paula Carroll. "Learning to Sparsify Travelling Salesman Problem Instances." International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer, Cham, 2021.

3. In Equation (6), why the parameter C is set to 10? Justification is required. 

4. In Tables 1 and 2, the improvement in terms of solution gaps is quite small, partially because all the methods can find very near-optimal solutions. I think some results from Appendix A should be presented and discussed in the main paper to justify this, for example the converging curves and detailed statistical test results. 

5. The comparison between the LKH variants ignoring preprocessing time in Appendix A is interesting and important, which demonstrates that the improvement of the proposed method comes from a better ML prediction rather than simply running for more trials. I think this result should be discussed in the main paper in particular. 

6. In Figure S.1, why does NeuroLKH start from with an objective value much smaller than that of other methods? From my understanding, all the methods start with the same random generated solution, and so the initial objective value should be the same. 

7. In figure S.1, why do LKH and VSR-LKH ignoring pre-processing time terminate earlier? What happens if letting them running for the same amount of time? 
limitations_and_societal_impact: The authors have adequately addressed the limitations of the proposed method, especially the generalization of the method to other TSP instances with different characteristics and other routing problems.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a framework for solving the traveling salesman problem by combining deep learning with the heuristic Lin-Kernighan-Helsgaun (LKH) algorithm. The basic idea is to use a sparse graph network model to transform edge distance and create edge candidate sets for LKH searching trials. The experiment results show that the proposed framework improves the performance of the LKH algorithm for TSP and its variations.
main_review: Originality: The paper uses the sparse graph network model to learn the edge scores with supervised learning and node penalties with unsupervised learning respectively. The output is then used to guide the original LKH algorithm. The entire framework combines the strength of deep learning and the traditional heuristic approach.

Quality: The paper is complete.

Clarity: The paper is clear to understand and easy to follow.

Significance: The authors claim that the proposed algorithm significantly outperforms the LKH algorithm. However, the experiment results only indicate a less than 0.1% improvement with 1000 instances under the same time limit for TSP when |V| = 100, 200, 500 respectively. Such marginal difference should not be considered statistically significant. This is a major weakness of the paper.

limitations_and_societal_impact: Some comments:

1) It is known that the LKH algorithm is powerful by itself. Given the marginal improvements (objective value) obtained by the proposed framework, I would expect some more intuitive illustration, such as a detailed analysis of an instance, to demonstrate how such framework adds value to boost or improve the original LKH algorithm. 

2) The entire framework is based on the LKH algorithm, which is known to be time-consuming. Usually one purpose of adding a deep learning wrap is to speed up the process. Thus, I would expect the authors to also show that the algorithm can achieve the same performance as LKH while significantly reducing the computational time.
review_title: null

Meta-review: The reviewers all agreed that the combination of learning techniques to augment traditional problem solvers is an exciting direction, and this paper adds to that direction.  Reviewer dK7t was ultimately convinced by the author's response and material in the appendix (Figure S.1) that the contribution was worthwhile even if the objective improvement was small in many of the TSPs.  I think the paper could be improved by directly addressing this in the paper: both the discussion of relative improvement and highlighting the larger improvements in other domains.

Decision: Accept (Poster)