Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: Authors tackle the problem of solving a capacitated vehicle routing problem (CVRP) when the cost of introducing an additional vehicle is introduced. Authors propose to use imitation learning with behavior cloning, and uses Google OR Tools as the expert policy. Then, the proposed model extract features with multiple layers of attention and make conditionally independent predictions across the adjacency matrix. It is nontrivial to extract the feasible solution from the probabilistic predictions, so greedy decoding, repair procedure, and post-processing with OR tools is employed.
main_review: One strength of this paper is that it identifies the common limitation of existing approaches in the literature: that they do not actually solve CVRP with hard constraints on the fleet size. Authors provide good explanation of why this violation is problematic for practical applications. Authors also propose a cost function that is motivated by prior work, which would facilitate future research.

Also, a good range of reinforcement learning baselines are considered in this work. This helps readers to understand the practical utility of the proposed method against alternatives.

However, I am not sure the proposed method is an effective way to impose fleet size constraint. The proposed model isn't really guaranteed to produce feasible solutions. In fact, a heuristic repair procedure is applied to meet the constraint, and then another heuristic post-processing with OR tools is used to improve the quality of the solution. It isn't clear to me why these methods are not applicable to existing approaches. In that sense, authors' modeling contribution seems to be orthogonal to the problem of enforcing the fleet size constraint. Also, the experiment section does not clearly describe the contribution of these heuristic post-processing steps. Ablation studies on these components would be desirable. In addition, the post-processing step in Section 4.3 is not described in detail.

The main experiment in Section 5.1 doesn't include the expert policy (Google's OR Tools) as a baseline. I think it is necessary, because it helps practitioners to understand in which situations they should be using conventional optimizers like OR Tools vs. ML methods, including the proposed one. I also believe the comparison of training time is not really fair- it is quite straightforward that an imitation learning algorithm is faster and easier to train. However, authors do not discuss the fact that their imitation learning method requires the expert policy to train, which is a dependency RL methods don't require.

Imitation learning.

Effect of each component is unclear.
summary_of_the_review: Authors have done a great job identifying a critical missing piece in the existing ML methods for CVRP. However, the proposed method relies on heavy heuristic engineering to enforce the constraint, and authors' modeling contributions seem orthogonal to the main problem (bounded fleet size) they are solving.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper demonstrate how to encode the CVRP with fixed fleet size into a set of input features that can be processed using a neural network derived from the permutation invariant pooling network architecture from Kaempfer and Wolf. They train the neural network using the Kaempfer and Wolf loss extended to penalize infeasible solutions. Lastly, unlike Kaempter and Wolf who use a beam search to convert the predictions made by the neural network into actual solutions, they use a greedy approach complemented by an OR solver to locally improve the solutions. 
main_review: The paper is clearly written, and nicely introduces the reader to the bounded CVRP problem. It provides ample details inits annex to help the interested reader dig further in the work. Last but not least, it improves quality of results compared to previous solutions while providing similar search time.

My main criticism is with regards to the evaluation. Since the technical solution is derived from the work of Kaempfer and Wolf, I would have liked to see the authors compare their solution against that of Kaempfer and Wolf both on the mTSP problem that Kaempfer and Wolf used in their paper and on the CVRP problem tackled in this paper.
Furthermore, since the authors introduce several refinements to the permutation invariant pooling network architecture, I would have liked to see a complete ablation study to get a sense of how much refinement helped. The paper only provides evidence that using softmax instead of softassign helps in table 5. In particular, I am curious to see how much of the improvement they get comes from the post processing step as opposed from the learnt representation.
Additionally, it would have been useful to see the optimal solution in the evaluation table. The authors were able to generate optimal solutions to build their training set, they should have also generated these solutions for their test set. This would have given us a sense of the significance of their improvement in QoR which is currently hard to evaluate since the baseline they used were designed to tackle a slightly different problem.
The author also claims outstanding training time compared to NeuRewriter. I am wondering why they didn't compare their training times against these of the baselines they used in table 1. Furthermore, they should explicitly state how time consuming was the generation of their large training set. 
summary_of_the_review: The paper propose incremental improvements to improve the work of Kaempfer and Wolf and adapt it to tackle the CVRP with bounded fleet size problem. The evaluation of this works needs improvement to trully demonstrate the value of each of these improvements.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper is the first to address the capacitated vehicle routing problem with a hybrid machine learning (ML) and algorithmic solution. They demonstrate that their approach is able to find good tour lengths for fixed fleet sizes. Solving the VRP with fixed fleet sizes is well motivated by the limitations faced by service providers.

main_review: ##########################################################################

 Pros:

-The goal of this paper, which is to develop an ML-based approach to the CVRP, is of significant practical interest and appears to be the first to do so.

-The claim of achieving competitive results to baselines that do not guarantee a fixed fleet size is supported by the experiments.

-The unique benefit of the approach, which is that it requires fewer vehicles albeit at slightly longer tour lengths, is validated by the results (particularly, in Table 1). However, it is unclear why Cost_v is not shown in Table 2.

##########################################################################

Cons: 

-The main contribution appears to be a formulation of the CVRP as a supervised ML problem. I don’t think this is motivated very well. Supervised learning requires a dataset of solved instances of the problem. This becomes prohibitively expensive to acquire for non-trivial problem sizes. To my understanding, this is why RL approaches have garnered most of the attention from this community up to now. Perhaps the authors can provide a convincing argument in support of pursuing supervised ML approaches in the rebuttal.

-I understand that at a high level the technical contribution is a deep learning architecture that can output a tour plan for a fixed fleet size and given CVRP problem instance, but I don’t know exactly what the novel technical component is. From my current understanding, a previous architecture used for the mTSP problem is being repurposed with slight modification. But it is not clear what these modifications are exactly based on the current presentation of the method, which is a bit difficult to parse, and it is hard to therefore assess this contribution. Other aspects of this framework, including the solution decoding algorithm, inference solution post-processing, memory-efficient loss, and auxiliary losses, seem to be ad-hoc with unclear novelty.

-In Section 2, the related methods are described but they are not contrasted with the contributions made by this paper.

-The ability of the model to generalize to out-of-distribution problem instances of the same size, and to problem instances of larger sizes than was trained on, is not explored in the experiments. This is a crucial aspect to test since it is necessary for real-world application.

-Realistic test instances were proposed in Uchoa et al., and the models in this work should evaluate on them.

-It is not clear why DPDP from Kool et al. 2021 is not included as a baseline.

-The claim that RL methods are cumbersome to train is not well supported in general. Indeed, the AM baseline is an RL method that achieves both slightly better tour lengths while being comparably efficient as the proposed method (Table 2). (Granted, it cannot solve the problems with fixed fleet size.)

-Please provide confidence intervals or std. dev. across multiple runs for the main quantitative results (Tables 1 and 2). 
 
References:

-Uchoa, Eduardo, et al. "New benchmark instances for the capacitated vehicle routing problem." European Journal of Operational Research 257.3 (2017): 845-858.

#########################################################################

Suggestions for improvement: 
 
-Figure 2 could use a more detailed caption with each high-level module explained. The content under “Encoder”, “Information Extraction” and “Decoder” in the text should match the figure. 

-Please define the sizes of vectors and shapes of matrices when introducing variables. 

-Clarify along what dimensions that softmaxes are applied in Equation 8 and to transform the compatibility scores of vehicles and edges.

-Prefer providing a text-based description of the (pseudo-)greedy decoding algorithm (Section 4.2) and deferring the pseudocode to the appendix. Also, the “pseudo” aspect of the decoding isn’t explained.

-Based on the ablation study in Appendix B1 for the auxiliary losses, it doesn’t seem like there is a significant difference in Cost/Cost_v performance. Therefore, it could help to simplify the presentation to remove the auxiliary losses from the model.
 

summary_of_the_review: I currently am recommending a borderline rejection for this paper. I believe the work is important since it is the first to propose a deep learning solution for the VRP with fixed fleet size. However, I have concerns related to the underlying motivation for the proposed supervised deep learning approach, the validity of a few of the claims and contributions, and have made significant suggestions to strengthen the experiments section. Altogether, this makes me feel the paper is not yet ready for publication. I welcome a response from the authors, particularly pertaining to my concerns related to the motivation and contributions.

================================================================================================

Update after rebuttal: While some of the minor concerns I raised were addressed by the paper revisions, the major concerns about the use of SL, the claim of superiority of the proposed end-to-end SL approach compared to RL approaches (particularly with regards to the efficiency experiment shown in Table 3), and the lack of clarity with respect to the precise technical contributions were not addressed. Therefore, I am maintaining my initial score of 5.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a supervised learning approach with a permutation invariant network to solve the Capacitated Vehicle Routing Problem (CVRP). Instead of assuming an unbounded fleet size, this model focuses on tackling the difficulty of constructing a complete tour plan with a specified fleet size and vehicle costs. The whole framework consists of an encoder, an information extractor, and a decoder. To guarantee the permutation invariance, the authors employ a separate embedding for each entity of the input with linear projection and design a permutation-invariant loss. The experiment results show that the proposed method works well for bounded fleet sizes CVRP and outperforms state-of-the-art RL models when considering fixed vehicle costs. Compared with other state-of-the-art algorithms, this supervised learning-based model is faster to train and provides competitive solutions with fewer vehicles.
main_review: Strengths:
1. This paper considers CVRPs with fleet size constraints and vehicle costs, which have not been studied by learning-based methods before. The proposed supervised learning model provides comparable results for standard CVRP and outperforms other learning-based methods accounting for fixed vehicle costs.

2. The model requires less training time when compared with other RL-based algorithms.

3. The model designs a special architecture to handle the permutation-invariant structure of CVRP, which is novel and insightful.

Weaknesses:
1. The whole framework is based on supervised learning, which requires a bunch of training data. For large-size CVRP, it is hard and time-consuming to get a near-optimal solution. The experiment results do not provide evidence that this model has any generalizability to large-scale problems, which could be a weakness of this paper.

2. The original definition of loss in equation (9) looks very computational-heavy, as it requires to compare every permutation, which the authors also mention it 'The calculation of the loss formulation in Equation 9 would induce considerable computational overhead, therefore a less memory-intensive formulation of the same loss is implemented (see Appendix C.5)'. However, it is unclear to me why the old loss function can be replaced with the new one. I cannot find any proof or explanation. I would expect the authors to provide more details. 

Some comments:
1. For training time comparison, I think the authors should also include the time of generating training sets for your supervised learning model, as other RL-based algorithms do not need. 

2. Some equations' are not very clear. For example, in equation (9), I cannot find the definition of $b_k$, I guess $b=b_k$. In equation (16), $b_k$ is defined, but I cannot find it in the equation.
summary_of_the_review: My decision is weak reject. 

The paper proposes a supervised learning algorithm to solve CVRPs with fleet size constraints and vehicle costs. The authors design a novel permutation invariant network to deal with the combinatorial structure. The experiment results show that the model has comparable performance for standard CVRP and outperforms other learning-based methods accounting for fixed vehicle costs.

However, my major concern is the generalization ability of this model. For large-scale CVRP (for example N > 500), simple google’s OR-Tools usually cannot provide near-optimal solutions, while LKH3 is very time-consuming. Therefore, generating a training set will be a big problem. I would change my mind if authors could come up with some ideas to improve or solve this problem.
review_title: null

Meta-review: This paper formulates and solves a capacitated vehicle routing problem (CVRP) in the presence of costs for deploying additional vehicles: a mixture of supervised learning, algorithms, and OR techniques is used. In particular, a mix of greedy decoding, repairing of the solution, and post-processing with OR tools is used to extract a feasible solution from the probabilistic prediction. 

The paper makes a good case that existing methods do not solve the CVRP with a hard constraint on the fleet size.  On the other hand, there is a strong dependence on heuristic improvements: e.g., a strongly dependence on the post-processing, and an additional repair procedure for the decoding process. The authors are encouraged to investigate how such improvements would work with existing approaches: i.e., how novel the new model’s contributions are.
Decision: Reject