Learning to Handle Complex Constraints for Vehicle Routing Problems

We thank the reviewer for constructive comments and acknowledging that our PIP is innovative, and extensively validated, and our paper is well-organized and clear. We understand the need for more discussion on related works, computational costs, and code release. We hope the response below and the added new experiments would clarify any misunderstandings and concerns.

[Discussion on [1][2]] Thank you for pointing out the references. We have reviewed them carefully and would like to clarify that our proposed PIP is mostly distinct from works [1] and [2], which correspond to [8] and [51] in the original paper, respectively.

• Regarding [1]: While both are early attempts to incorporate Lagrangian multiplier into NCO, [1] is designed for iterative solvers for soft-constrained VRPs, whereas PIP is for constructive solvers for hard-constrained VRPs. Moreover, our primary motivation for using the Lagrangian multiplier is to enhance our model's initial constraint awareness. Unlike [1], we argue and show that using Lagrangian multiplier alone is less effective for complex constraints. To address this, we propose our novel PIP and PIP-D, which effectively overcome this weakness and improve overall performance.
• Regarding [2]: While both use masking to prevent infeasible solutions, our preventive infeasibility (PI) masking differs from the "global mask function" in [2]. Firstly, although [2] shows the effectiveness of their global masking for a specific case of CVRP with limited vehicles, our PI masking is technically different and serves as a more generic framework to address complex VRP variants where feasibility masking is NP-hard. Also, we employ an auxiliary decoder to predict PI masking, and our PIP has been validated on complex constrained variants like TSPTW and TSPDL, as well as on various autoregressive and non-autoregressive neural solvers such as AM, POMO, and GFACS, demonstrating broader applicability. Moreover, [2] primarily focuses on scalability, whereas our work emphasizes constraint handling. We note that our work can be coupled with [2] in future work, and we will discuss more in the revised paper.
• Lastly, as acknowledged by Reviewer #DEtT, we are among the first to address the complex interdependent constraints that make masking NP-hard, a point not covered in existing NCO works like [1][2].

[Code Release] As promised in line 276, we will make our code, pre-trained models, and the used data publicly available on GitHub. Following the rebuttal guidelines, we have forwarded our code to the Area Chair.

[How to obtain the training label] Yes, getting global and accurate masks is expensive (as mentioned in lines 139-150). Hence, in our PIP, we employ a one-step approximation to balance computational costs without iterating over all future possibilities which is NP-hard (see results on such balance in Table R3 and R4 of the attached PDF). The training label is such one-step masking, determined by evaluating whether selecting a candidate node would lead to irreversible future infeasibility for the remaining unvisited nodes in the next step. If so, the candidate is considered infeasible at that step. Detailed examples and descriptions are available in lines 192-195 and Appendix A.3.

[More literature review] We have included most recent work from NCO field and will add more from OR field. Any suggestions are warmly welcome!

[Additional experiments]

• Regarding real-world datasets, we have evaluated our PIP(-D) to unseen real-world instances in benchmark dataset [76] with different scales, distributions and constraint hardness in Appendix D.6 (Table 7). Additionally, we conducted extensive experiments on complex variants like TSPTW and TSPDL, covering various levels of constraint hardness (Easy, Medium, Hard). Results suggest that our PIP(-D) can generalize to real-world datasets with unknown constraint hardness.
• Regarding other VRP variants, we follow your suggestion and explore the application of our PIP framework (Lagrangian multiplier, PI masking and the auxiliary decoder) to VRPs with various complex constraints, such as VRPBLTW (VRP with constraints of capacity, backhaul, duration limit, and time window). We found that in such variants PI masking is less important since we can obtain the masking easily at each constructive step, but the Lagrangian multiplier and the auxiliary decoder still have effects. The results demonstrate that our PIP framework significantly enhances solution quality on VRPBLTW-50 (Our gap 1.80% vs. POMO's gap 9.17%, see Figure R1 for details).
• Lastly, our PIP has potential beyond VRPs, such as in job shop scheduling, where operations require a specific order. PIP can proactively prevent infeasibility in these cases, and we leave them as future work.

[How our PIP advances the SOTA] Firstly, our PIP is generic to boost an existing SOTA constructive neural VRP solver to enhance its capability of constraint handling. We have verified our effectiveness on both autoregressive (AM, POMO) and non-autoregressive (GFACS) solvers. Additionally, we have conducted newexperiments by further coupling our PIP with LKH3 (see General Response #2 for more details).

[Computational efficiency] Please kindly refer to our General Response #1.

[Theoretical analysis] We acknowledge that the NCO domain primarily relies on empirical results and often lacks theoretical support for most of published papers. Our findings are backed by extensive results, demonstrating empirical superiority with significant improvements in infeasibility rates and solution quality. Nevertheless, we provide some more rigour analysis for our PIP, please refer to the second response to Reviewer #azSu.

[Robustness under different hardness] Thanks for the suggestion. We have discussed the mentioned experiments in benchmark datasets in Appendix D.6 (Table 7). We will add more analysis.

We appreciate the reviewer’s kind effort in providing insightful and detailed feedback. We are delighted that the reviewer finds our work to be novel, well-structured, and effective in addressing feasibility issues. We have conducted additional experiments to address your comments and hope the following response and results will clear any remaining concerns.

[Computational cost (Q1, W1)] Thank you for your valuable comment! We apologize for any confusion. Please refer to our General Response #1 for detailed discussion on computational costs. In summary, while our PIP introduces some unavoidable overhead to the backbone model, this is offset by its strong effectiveness. As shown by our additional results in Table R1 of the attached PDF, even with extended inference times, existing baseline methods still struggle with constraint handling and may fail to find any feasible solutions. In addition, we have employed strategies like one-step PI masking, an auxiliary PIP-D decoder, and a sparse strategy to further mitigate the costs. We now provide more responses:

• PIP does not always double the computational time of the backbone solvers. For instance, on small-scale TSPTW-50, POMO* takes 13s while POMO*+PIP takes a similar time of 15s; on larger-scale TSPTW-500, we can leverage the sparse strategy to reduce the overhead - as shown in Table 3, our GFACS*+(PIP; PIP-D) demonstrates similar inference times to GFACS* (6.5m vs. 6.4m), while significantly reducing infeasibility (57.81% vs. 1.56%; 0.00%) and improving solution quality (21.32% vs. 15.04%; 11.95%), showing great efficiency.
• The auxiliary decoder aims to approximate the one-step PI masking to avoid its frequent calculation during training. Results show that PIP-D significantly reduces the training time (e.g. by 1.5x on TSPTW-50) compared to PIP. As the inference overhead is rather insignificant than other baselines, we employ the complete one-step PI masking to guide the construction process.
• For Q1 - Yes, $T_{PIP}\\approx T_{POMO∗+PIP}- T_ {POMO∗}$, which results from the acquisition of the PI masking. Detailed examples and descriptions are available in lines 192-195 and Appendix A.3. And please kindly see our next response for discussions of computational time balance.

[PIP with different step numbers (Q2, W2)] Insightful comment! Yes, zero-step PIP differs from the baselines. Following the suggestion of the reviewer, we have further supplemented this by conducting new experiments on PIP and PIP-D with different step numbers. In Table R3, R4 attached in the PDF under General Response, we gather the results (solution feasibility and quality) and the inference time for different PIP steps. Results suggest that zero-step PIP saves some time but suffers from inferior performance, while the two-step PIP improves performance slightly but is computationally expensive. However, one-step PIP balances these trade-offs effectively. We will further clarify this in the revised paper.

[Apply PIP to more VRPs with various complex constraints (W3)] Thank you for the suggestion. We agree that the title "Travelling Salesman Problems" might be more appropriate for our original paper. Nonetheless, we plan to follow the reviewer's suggestions and further explore applying our PIP framework to VRPs with more complex constraints, such as VRPBLTW (with capacity, backhaul, duration limit, and time window constraints). Results on VRPBLTW-50, presented in Figure R1 of the PDF under General Response, show that our PIP framework significantly enhances solution quality for VRPs with complex constraints (our gap 1.80% vs. POMO's gap 9.17%). While our PIP framework may not be a silver bullet for improving performance across all VRP variants, it has been successfully applied to variants like TSPTW and TSPDL, covering various levels of constraint hardness (Easy, Medium, Hard). Moreover, we believe that our PIP framework has potential applications beyond VRPs, such as in job shop scheduling, where operations need to be completed in a specific order and infeasibility can be proactively prevented. We plan to explore these applications as future work and will discuss them further in the revised paper.

[Comparison with LKH3 with time limit (Q3, W4)] Thanks for the insightful comment. We follow your constructive suggestion and add Table R2, Figures R2 and R3 (presenting the progress of the objective value and infeasible rate over different inference time) in the attached PDF under global response. Details are discussed in our General Response #2.

To sum up, we agree with the reviewers that LKH3 can generate near-optimal solutions for TSP-100 within a few seconds. However, when given a limited budget, LKH3 performs significantly worse than our POMO*+PIP-D on the studied complex variants. As shown in Table R2, while LKH3 is powerful with state-of-the-art quality, its advantage diminishes with limited time. Our POMO*+PIP-D reduces the infeasibility rate from 53.11% to 6.28% with 0.9s time per instance, compared to LKH3 with 5.1s time. To leverage the strengths of both approaches, we conducted an additional experiment using our PIP-D to provide better initial solutions for LKH3. This further reduces the infeasibility rate from 53.11% to 0.21% and improves the objective from 51.65 to 51.25 within only a few seconds. Notably, initializing LKH3 with POMO*+PIP-D outperforms the default LKH3 setup (10,000 trials), achieving slightly better solution quality while using only 27% of the inference time (9 hours vs. 1.4 days).

Regarding the stopping criteria for each algorithm (i.e., to restrain its runtime):

• For LKH3, we set a fixed number of max trials following the conventions in NCO;
• For neural algorithms, we
  • sample a pre-set number of solutions ($N_s$) for each instance: $N_s=8$ for POMO series models and $N_s=1280$ AM series models;
  • predefine 100 ants and 10 pheromone iterations for GFACS.

Table R8: Results on POMO*+PIP(-D)+LKH3 with the similar $\underline{\text {total inference time}}$ limit as doubled time used in POMO*+PIP(-D).

Table R9: Results on LKH3 with the similar $\underline{\text {instance inference time}}$ limit as GFACS*+PIP(-D) (+LKH3) on $n=500$ (first 10 instances).

Table R7: Results on POMO*+PIP(-D)+LKH3 with the similar $\underline{\text {instance inference time}}$ limit as doubled time used in POMO*+PIP(-D).

Table R6: Results on LKH3 with the similar $\underline{\text {total inference time}}$ limit as POMO*+PIP(-D).

Table R5: Results on LKH3 with the similar $\underline{\text {instance inference time}}$ limit as POMO*+PIP(-D).

We thank the reviewer for recognizing our work as being with good perspective and very clear description. We understand that the main concerns are the computational cost and applicability towards real-world scenarios. We hope our response below will address them.

[Our PIP addresses shortcomings of the Lagrange multiplier method (W1)] For original neural solvers, constraint awareness merely comes from the feasibility masking. However, the masking itself is NP-Hard in more complex variants, necessitating the use of a Lagrange multiplier to make the models aware of the constraints, thereby guiding the policy optimization. However, its advantages diminish as problem complexity increases (see Figure 2 and lines 312-323, where we provide in-depth discussions for the pros and cons of the Lagrange multiplier). For instance, in Hard datasets, the infeasible rate of POMO* (i.e., only with the Lagrange multiplier) is 100%. However, when equipped with our PIP-D, it drops dramatically to 6.48%. Therefore, only using the Lagrange multiplier is not enough for solving complex VRPs, while our PIP can address this shortcoming. We will refine the introduction and clearly mention this point in the revised paper.

[Computational complexity (W2)] We understand the reviewer’s concern, as the acquisition of accurate masking is NP-Hard. We have implemented several strategies to enhance computational efficiency of our PIP-D, including one-step approximation of the PI masking, auxiliary decoder (PIP-D) to avoid intensive calculations of PI masking during training, and sparse strategy for large-scale datasets. The empirical results verify their effectiveness even facing large-scale instances. Please refer to General Response #1.

[Scalability (W3)] We acknowledge that scalability is a significant challenge in NCO, and numerous concurrent works [10, 18, 21, 23, 48-52] are exploring scalable algorithms. However, we would like to clarify that practical applications of NCO require not only scalability but also the ability to handle complex constraints.

• Complex Constraints: Our PIP is an early work to address the complex constraint handling in VRPs, whose significance is acknowledged by the reviewer.
• Scalability and Generality: Our PIP is orthogonal to scalability research and can be combined with scalable algorithms. We have demonstrated our framework's generality and scalability using GFACS [10] on TSPTW-500. Note that scalability limitations often arise from the backbone itself. Our method can solve large-scale instances as long as the backbone model is capable of doing so.

[Potential challenges and limitations in scaling PIP to larger and more complex COPs (Q1)]

• Larger Scale: The main challenge and limitation is the trade-off between computation and performance. As acquiring the accurate feasibility masking is costly on large-scale instances due to the NP-Hard nature, we have to make some approximations and reduction of the search space to decrease overheads, which may sacrifice the solution quality and feasibility. Although our PIP has implemented approximation methods (e.g. one-step PI masking and auxiliary decoder to replace its acquisition), and can be applied to scalable neural solvers (e.g. GFACS), we cannot guarantee consistent performance across all scales (as noted in lines 346-351). A more effective and efficient approximation technique may be beneficial. To further reduce overheads, we also discuss some possible ways in the response to the next question.
• More Complex COPs: As noted in lines 346-351, our PIP framework may not universally improve performance across all VRP variants, necessitating further experiments on various COPs. Another potential limitation is the adaptability of the PIP framework to all complex VRPs. We identify two types of complex VRPs: those with NP-Hard masking (solvable by PIP) and those with non NP-Hard masking but with large optimality gaps due to complex constraints. For the latter, PI masking is no longer necessary since we can obtain the feasibility masking easily at each constructive step, but the Lagrangian multiplier and the auxiliary decoder still have effects. Please see Figure R1 of the attached PDF, where we explored the application of PIP to VRPBLTW.

[Further trials to reduce the computational complexity (Q2)] Below strategies can be considered for further accelerating the training and inference of PIP:

• Apply sparse strategies to refine PIP calculations:
  • Only consider top K neighbours. We have implemented this strategy on GFACS. Results in Table 3 show that GFACS*+PIP-D maintains similar training and inference times as GFACS* on TSPTW-500 (i.e., 28.3h/6.5m vs. 28.1h/6.4m).
  • Employ a trainable heatmap to confine the candidate space of PIP calculations. Recent heatmap-based methods have successfully reduced the search space during construction, and we see similar potential for heatmaps to confine the candidate space of PIP calculation.
• Couple with the state-of-the-art solvers (e.g. LKH3): Our PIP is empirically verified to be efficient due to its capability to obtain good and feasible solutions within a very short time (LKH3: 1.4d vs POMO*+PIP-D: 48s). By further coupling with LKH3, our PIP can even achieve the performance of LKH3 within a few hours (9h). Details refer to General Response #2.
• Fine-tune Lagrangian method (*) with PI masking: We found that PI masking does not need to be calculated throughout the entire training process. Fine-tuning a pre-trained Lagrangian method (e.g., POMO*) with PIP for a few epochs will also deliver competitive results. Details can be found in Appendix D.3.
• Early stop of PI masking: We empirically observed that infeasibility primarily occurs in the initial steps of the construction process. Hence, it is possible to employ PIP only during these early stages. Details can be found in Appendix D.4.

The authors have provided extensive comments and new results in response to the criticisms raised in your reviews. Has this response addressed your main concerns? If not, are there additional questions you would like to pose? The author discussion period is scheduled to end tomorrow (Aug 15). Please respond.

We appreciate the reviewer for the positive and valuable comments. We are delighted that the reviewer found our approach adaptable to complex constraints, effective and flexible. We hope that the following response, along with additional experiments, will address remaining concerns.

[Generalization Evaluation (W1)] We have evaluated the generalization of our PIP(-D) to the unseen real-world instances in datasets [76] with different scales, distributions (e.g. node distributions, time window distributions and width) and constraint hardness in the original Appendix D.6 (Table 7). The results consistently showcase that our PIP(-D) could significantly reduce the infeasible rate and improve solution quality on in-distribution (Table 1,2,3) and out-of-distribution (Table 7) datasets.

[Theoretical analysis of PIP (W2)] We acknowledge that the NCO domain is mainly built on empirical superiority, prioritizing in closing gaps between neural and traditional solvers, but lacks theoretical support.

• Regarding empirical superiority: Our PIP(-D) has been applied to various constructive methods, including both autoregressive (AM, POMO) and non-autoregressive (GFACS) models. We have conducted extensive experiments on TSPTW and TSPDL with different constraint hardness levels, from small problem scales (50, 100) for AM and POMO to large scales (500) for GFACS. These experiments demonstrate significant reductions in infeasibility rates and substantial improvements in solution quality.
• Regarding theoretical support, we would like to note that each component of our PIP(-D) does have some theoretical support.
  • Lagrangian Multiplier Method: we represent an early trial to incorporate the Lagrangian multiplier method into constructive VRP solvers by interleaving constraints into the reward function, transitioning from Eq. (2) to Eq.(3), both of which are theoretically proven to be equivalent in [8].
  • PI Masking and Auxiliary Decoder: As illustrated in Figure 1, the feasibility masking (i.e., $n$-step PIP) in complex constraints is NP-Hard. While iterating over all future possibilities would make PI masking complete, it is computationally inefficient. Therefore, we approximate it with one-step PI masking, whose efficiency is validated in Table R3 and R4 of the attached PDF. To enhance training efficiency, we use an auxiliary decoder to further approximate one-step PI masking, avoiding the need to acquire it continuously during training (see lines 293-296).

We agree with the reviewer that theoretical justification is significant and acknowledge the need for further theoretical development, which we leave as a future work.

[Comparison with LKH3 with time limit (W3, Q5)] We follow the suggestion and add experiments on our PIP(-D) and LKH3 with various time limits (from 5s to 3m per instance). We exhibit a comprehensive comparison in Table R2 and Figures R2 and R3 of the attached PDF, where our PIP outperforms LKH3 within limited time budget and achieves slightly better solution quality while using only 27% of the inference time (9 hours vs. 1.4 days) by further coupling with LKH3. For details please refer to General Response #2.

[Can our PIP apply to methods other than constructive methods? (Q1)] Yes, our PIP can potentially be applied to most NCO methods.

• Constructive Methods: We have validated its effectiveness on both autoregressive (AM, POMO) and non-autoregressive (GFACS) methods.
• Iterative Methods:
  • Our PIP can provide better initial solutions to enhance search efficiency, as demonstrated in Table R2 of the attached PDF.
  • While the logic of iterative search differs from construction, making one-step PIP masking less applicable, components of our PIP framework, such as the Lagrangian multiplier method for constraint awareness and the auxiliary decoder for learning infeasibility, can still guide the search to avoid infeasibility. We consider it as a promising direction for future work.

[Can the infeasible constructed solutions be recovered by local search? (Q2)] We conduct additional experiments using LKH3 with different sources of initial solutions. The results indicate that local search methods can recover infeasible solutions. However, our PIP-D provides the most promising (good and mostly feasible) initial solutions for LKH3, enhancing its search efficiency and achieving SOTA performance (see Table R2 in the attached PDF). This suggests the promising potential of our PIP-D to assist strong heuristic solvers in future work.

[Generalizability of PIP to different datasets in different domains (Q3, Q4)] We would like to clarify that our PIP is not tailored to the training datasets since it is a generic framework with the potential to be applied to different backbone models; that is, what the backbones can do, our PIP adapted to them can also achieve.

• Regarding VRPs: We have conducted extensive experiments on both in-distribution and OOD datasets of variants like TSPTW and TSPDL, covering various levels of constraint hardness (Easy, Medium, Hard). Our PIP consistently outperforms other baselines in these scenarios. Although PIP may not universally improve performance across all VRP variants, we followed the reviewer's suggestions and explored its application to VRPs with various complex constraints, such as VRPBLTW-50 (VRP with constraints of capacity, backhaul, duration limit, and time window). Results demonstrate that PIP significantly enhances solution quality for VRPs with complex constraints (Our gap 1.80% vs. POMO's gap 9.17%, see Figure R1 of the attached PDF for more details).
• Regarding a broader range of COPs: Beyond VRPs, our PIP has potential applications in other domains, such as job shop scheduling, where operations need to be completed in a specific order. Infeasibility can be proactively prevented using PIP. We plan to explore these applications as future work.