Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The present submission is concerned with dynamic programming (DP) methods for  traveling salesperson problems and a capacitated vehicle problem. Since DP for these problems struggles with enormous DP table sizes, the authors propose to heuristically prune the DP table using a neural network. 

Essentially, the idea is to leverage recent approaches that use neural network to predict good solutions for combinatorial optimization problems. In this particular case, a neural network is used to predict partial solutions, and these in turn allow the others to compute priority values for the edges. High priority edges are preferred in the solution expansion step of the DP.

The contribution of the paper is the evaluation of the approach (which, according to the authors, has not been tried before); the neural network itself stems from the literature (with few modifications).
main_review: The paper is generally well written and nicely illustrated. The only two aspects of the writeup that I found lacking was that none of the considered problems are defined in the paper, not even informally; and that not all column labels in the computational tables are defined. 

I found the proposed approach intriguing. From the combinatorial optimization point of view, I feel it is more attractive to combine DP and neural networks than to use neural networks directly to predict good solutions. Additionally, it seems that the approach is easily applied to other problems as well, provided there is a DP scheme and a suitable neural network; nothing in the approach is really specific to vehicle routing/TSP. On the other hand, the approach does away with a major benefit of DP, namely, that optimality may be guaranteed. In fact, there are no theoretical guarantees.

The computational experiments are extensive:

- For the TSP, the authors compare to a large body of literature including the Concorde TSP solver which is a staple in the combinatorial optimization community. Indeed, the results look favorable for Concorde (Concorde finds a better solution while requiring only one fourth of the running time), although the authors approach seems to be superior to the other algorithms from the literature. 

- For the VRP, the authors compare to genetic algorithms and an ancient DP approach. The authors approach offers a speed-up of about a factor of 10 at the expense of losing 2 percent of the solution quality. The approach is unable to find competitive solutions even if allowed several times the running time of the approaches from the literature. Hence, the usefulness of the approach depends on the trade-offs that the user is willing to make.

- TSP with time windows: The authors compare against a combination of constraint programming and learning, and against a local search appraoch. This time, the results look largely favorable for the new approach.

Overall, however, the choice of reference algorithms seems a bit arbitrary; I found the text did not make clear why were these particular algorithms chosen and others were not. For instance, reference [1] is not included in the VRP experiments. The benchmark instances for TSP stem from another learning publication; what about the standard TSPlib benchmark?


limitations_and_societal_impact: My conclusion from the experiments is that the proposed approach is promising, but I am not convinced that it would beat mathematical programming based approaches, even though these would certainly be the method of choice in combinatorial optimization/operations research where TSP/VRP originates and is heavily studied. Indeed, the only math. programming approach (Concorde) included in the comparison turns out to be superior. To illuminate this question, further literature review and extended benchmarks with new instance sets from the OR community would be required.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper investigates dynamic programming techniques for routing that relies on auxiliary neural network models. The idea is to predict a "heatmap" of edges indicating whether they are promising or not for good-quality solutions, which needs to be generated only once per instance. The problem is then solved by a (forward) dynamic program that expands states based on scores extracted by the heatmap. The methodology is applied to the vehicle routing problem (VRP), the traveling salesperson problem (TSP), and the TSP with time windows (TSPTW).
main_review: **Originality**

I believe the key ideas underlying the paper are somewhat incremental, albeit nicely combined together. More specifically, the methodology is conceptually close to a value-function approximation that is defined in terms of their scoring policy. Thus, it is akin to a reinforcement learning approach and builds upon many of the references that the authors appropriately cite but do not discuss or highlight appropriately, in my view.

In particular, deep learning has been used to guide tree search (e.g., references [26] and [34] in the paper). The differences here, to the best of my knowledge, are (a) the routing applications, (b) the fact that authors expand DP states (allowing them to break some symmetry and dominance) and not tree nodes; and (c) the heatmap and beam search implementation for DPs. I would strongly suggest the authors to extend their related work discussion to make this comparison clearer.

**Quality**

My major concern in terms of quality is that results still read as somewhat preliminary (which seems to be still consistent with the previous ICML comments as well).

Indeed, there are improvements with respect to the neural network approaches evaluated by the authors and the TSPTW results are meaningful. However, it does not seem that the paper outperforms exact approaches for small instances (e.g., Concorde/TSP) nor standard heuristic techniques (e.g., LKH/VRP) in several settings. The overall tradeoffs between their technique (considering the implementation complexities/training) and other methods are not clear.

Moreover, the scalability benefits mentioned by the authors was not investigated further; for example, authors do not indicate whether their method really scales for instances with significant more nodes (e.g., a few thousand).

**Clarity**

The paper is well written. I believe the results are mostly reproduceable, though there are a few parameters based on "educated guesses" as indicated by the authors. Some further discussion concerning training and limitations could have also been beneficial.

**Significance**

In my view, the paper presents meaningful and interesting ideas, but still requires a stronger experimental section to be of interest beyond a specific area (i.e., deep learning models to routing problems). For example, authors could demonstrate the scalability of their method to instances with a few thousand nodes, which is common in papers investigating LKH-3. Connection to existing works must also be presented in much more details.
limitations_and_societal_impact: No direct negative societal impacts to the best of my knowledge.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes a framework for solving vehicle routing problems, based on a combination of supervised learning and dynamic programming. The proposed method is an extension of the restricted dynamic programming algorithm where at each iteration, the selection of the (fixed number of) most promising solutions is done by a learning-based heuristic. The framework is tested on instances of 100 nodes of the TSP, CVRP and TSP with time windows. 

main_review: Originality
---------------
The novelty of this work is the use of a learned heuristic to define the criteria upon which the most promising states are selected in a restricted dynamic programming algorithm. The criteria is based on a heat map provided by an existing pretrained neural network and a “potential” formula that is handcrafted by the authors.  

The contributions are clearly positioned w.r.t related works.

Quality
----------
The paper is of high quality. The explanation of how the framework is adapted for each of the 3 routing problems is clear. 
The authors discuss both the strengths and limitations of their work and do not overclaim their contribution. 
I appreciated the comparison to a stronger (non-learned) heuristic baseline (HGS) for the VRP experiments. 

Regarding the framework itself, I wonder how it differs from a beam search using the same scoring function (heat+potential) with the elimination of dominated solutions at each step. Or an A* algorithm with the same elimination trick. In other words, what is "dynamic programming-specific" about this framework?

Clarity
---------
The paper is very well-written and easy to follow. 

Details:
* I found confusing that at L112 “state variables” are defined as triplets (visited, current, cost) and then  L122 “DP state” is defined as only (visited, current) 
* Figure 3 titles and legends fonts are too small 
* L189 "travel time is equal to cost/distance" not clear 
* L337 We *believe*

Significance
----------------
Th proposed framework is flexible and able to naturally handle constraints, which is a big strength compared to other NCO methods.

However, the reported results are slightly better or close to the best existing NCO methods but still not as good as specialized algorithms. And these results were obtained on graphs of size 100, which is relatively small compared to what can be solved, both with specialized methods and NCO today. For instance the cited reference [17] solves TSP problems with up to 10,000 nodes. As noted by the authors, standard VRP benchmarks have instances of 100 to 1000 nodes. 

The authors note that scaling is challenging because of the “fully-connected O(n^2) GNN” but this GNN is an essential ingredient of their framework so it’s not clear if/how this framework can scale.

Therefore despite the high quality of the paper, I feel like it is quite an incremental contribution.





limitations_and_societal_impact: Yes, in the checklist.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a framework for solving vehicle routing problems by combining the strength of deep learning and dynamic programming. The basic idea is to use a graph neural network to restrict the search space and then boost the DP algorithm. The experiment results for the traveling salesman problem (TSP), the vehicle routing problem (VRP), and TSP with time windows (TSPTW) show that the proposed method can achieve similar performance as LKH and outperform most other neural nets-based algorithms.
main_review: Originality: This work employs a framework of using learned neural heuristics to guide dynamic programming algorithms. The model consists of a GNN [3] and a beam search. I think this framework is not completely novel but solid enough.

Quality: The paper is solid. Authors provide experiments with detailed analysis.

Clarity: The paper is clearly written and easy to follow.

Significance: The proposed framework exhibits good generalization towards different vehicle routing problems, as it can efficiently handle hard constraints. Meanwhile, the experiment results demonstrate that the model outperforms the state-of-art algorithm to solve TSPTW, which is impressive. However, it still does not beat some other algorithms [1, 2] for CVRP.

[1] Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, Nadia Lahrichi, and Walter Rei. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3):611–624, 2012.

[2] Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2020.

[3] 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.
limitations_and_societal_impact: Some comments:

1)  I think this framework has very good generalizability and is very promising for solving other problems. I encourage the authors to apply this framework to other graph-related combinatorial optimization problems (for example, job scheduling).
review_title: null

Meta-review: The paper presents a neural network based approach to dynamic programming with large state spaces and applies it to traveling salesman and vehicle routing problems. While the paper is well written and interesting, the experimental side is preventing acceptance at NeurIPS. In particular, while it is not strictly needed to outperform competitors, the theoretical novelty just needs to be larger to merit publication.

In order to better prove the merit of the presented approach, running the algorithm on problems where dynamic programming is a better methodology than TSP might be one avenue, as suggested by the reviewers.
Decision: Reject