Adaptive Constrained Optimization for Neural Vehicle Routing

Thanks for dedicating your time to reviewing our paper! Your suggestions are very constructive for us to further improve the paper. Please find our detailed response below.

Response to “… the formulation of HV …”

Thank you for your insightful and constructive comment. In our experiments, we employ the standard normalized hypervolume (HV) metric [1,2]. Its formulation on two-objective minimization problems is given by:

$\text{HV}(\mathbf{f}) = \prod_{j=1}^{2} \left( \frac{z_j^{\mathrm{ref}} - f_j}{z_j^{\mathrm{ref}} - z_j^{\mathrm{ideal}}} \right)$

where $(f_1, f_2)$ denote the two objective values, i.e., the infeasibility rate and the optimality gap in our experiments. The terms $(z_1^{\text{ref}}, z_2^{\text{ref}})$ are the reference values, while $(z_1^{\text{ideal}}, z_2^{\text{ideal}})$ represent the ideal values, which are set to zero in our experiments.

This normalized HV metric effectively captures the overall optimization performance by simultaneously reflecting both feasibility and optimality. Since the two objectives have comparable numerical scales, their contributions to the HV value are approximately balanced. As a result, even when improvements are made in only one aspect (e.g., on TSPDL100), the HV metric remains capable of distinguishing the better-performing methods.

We sincerely appreciate your helpful comment and hope this explanation addresses your concern.

[1] Multicriteria Optimization. Springer, 2005. [2] Performance assessment of multiobjective optimizers: An analysis and review. IEEE TEvC, 2003

Response to “... the scale of the questions for comparison is limited ...”

Thank you for your constructive and valuable suggestions. Although TSPTW (DL) with $N = 100$ and $N=50$ already poses significant challenges to existing approaches, we fully agree that the problem scale in our current experiments is relatively limited.

In response, we extend our evaluation to larger-scale and real-world datasets by integrating the proposed ICO method with the recently developed RELD model [3], which is specifically designed for cross-instance generalization. Both RELD and RELD + ICO are trained on instances with $N \sim \mathcal{U}[40, 70]$, and evaluated on larger-scale datasets, including TSPTW200-medium and real-world TSPLIB instances. This setup enables a more comprehensive assessment of the generalization ability of our method under substantial shifts in problem scale and distribution.

Generalization to TSPTW200 (medium difficulty)

Generalization to TSPLIB ($N\le 200$, medium difficulty)

Note that the backbones POMO, PIP, and RELD are all trained with Lagrangian relaxation. These experimental results summarized above demonstrate that:

1. RELD + ICO consistently outperforms other methods in terms of both optimality and feasibility on larger-scale and real-world datasets, highlighting the robustness and scalability of the proposed approach.
2. Compared to PIP, which requires computing a mask with cubic time complexity in the number of nodes, our method can eliminate the need for such expensive computation on large-scale problems. In our experiments on TSPTW200, RELD + ICO achieves a significant reduction in inference time (316s to 54s) while maintaining higher solution quality and ensuring 0% infeasibility.

We will revise our paper to include these new experiments and analysis. Thank you again for your valuable suggestion, which has helped us further strengthen our experimental design.

[3] Rethinking Light Decoder-based Solvers for Vehicle Routing Problems, ICLR 2025.

Response to minor issues

Thank you for your kind reminder. “PIP” refers to Proactive Infeasibility Prevention. We will revise the paper to make this abbreviation clear. As for the ablation experiments, we will consider shrinking our methodology and experiment setup sections to leave more space for those interesting experiments. Thank you again for your valuable suggestions!

---

We hope that our response has addressed your concerns, but if we missed anything, please let us know.

Thanks for dedicating your time to reviewing our paper! Your suggestions are very constructive for us to further improve the paper. Please find our detailed response below.

Response to “... adjustment of fixed Lagrangian multipliers … This singular focus may limit the perceived novelty of the contribution”

Thank you for your valuable and constructive feedback. Targeting important constrained combinatorial problems with broad applications, the contributions of this paper have two folds:

1. Conceptual Contribution: To the best of our knowledge, we are the first to reveal the limitations of using a policy-level Lagrangian multiplier (i.e., a single $\lambda$) in neural combinatorial optimization. This insight can help to rectify a common but suboptimal practice and, we believe, contribute meaningfully to further development of this research direction.
2. Technical Contribution: Building on this conceptual insight, we propose a sound instance-level multiplier formulation. We design an effective multiplier-conditioned policy and successfully incorporate the iterative Lagrangian algorithm into both training and inference. Extensive experiments and ablation studies demonstrate the effectiveness of each component of our method.

While our method may appear relatively simple—without introducing novel architectures or complex algorithms—we emphasize that the primary contribution of this work lies in its conceptual advancement. We believe this perspective can inspire future research in constrained VRP and encourage a more principled use of Lagrangian training methods, beyond fixed penalty weights. In fact, the simplicity of our approach enables a model-agnostic framework, which can be readily applied to other RL-based backbones such as pure POMO and RELD [1] (see the next response). Thank you again for your valuable feedback. We will revise our paper to include more discussions and clarifications.

[1] Rethinking Light Decoder-based Solvers for Vehicle Routing Problems, ICLR 2025.

Response to “... it does not consistently outperform the PIP model... ”

Thank you very much for your valuable and constructive feedback. We would like to begin by revisiting the experimental results. Across the four datasets (TSPTW50/100 and TSPDL50/100) and three evaluation metrics (Infeasibility Rate, Gap, and HV), our proposed ICO method outperforms all PIP baselines in 11 out of 12 cases. The only exception is the feasibility rate on TSPDL100. While we acknowledge that some improvements are modest, we believe the overall performance gain is sufficient to justify the contribution and effectiveness of our method.

In addition, the superiority of our proposed ICO extends beyond incremental performance gain in the following two key aspects:

1. Model-Agnostic Framework: Our method is not tailored specifically to the PIP model; rather, it can be integrated into a wide range of RL-based backbones. To demonstrate this, we conducted additional experiments combining ICO with both pure POMO and RELD [1]—the latter being a recent method designed for cross-instance generalization with a more complex decoder. Following the generalization setting of RELD, we trained both RELD and RELD + ICO on instances with node size $N \sim \mathcal{U}[40,70]$, and evaluated them on the larger TSPTW200-medium dataset, which allows us to assess the generalization capability under a shift in problem scale. The results summarized below show that ICO consistently improves the performance over POMO and RELD, even on unseen larger instances, underscoring its effectiveness and general applicability across different architectures.

2. Efficiency on solving large-scale problems: Compared to PIP, which requires computing a mask with cubic time complexity in the number of nodes, our method can eliminate the need for such expensive computation in some cases. For example, on large instances with $N=200$, RELD + ICO achieves a significant reduction in inference time (316s to 54s) while maintaining high solution quality and ensuring 0% infeasibility, as shown in the last table.

Combined with POMO on TSPTW50 (Medium Difficulty)

Combined with POMO on TSPDL50 (Medium Difficulty)

Combined with RELD and generalization to TSPTW200 (Medium Difficulty)

We sincerely appreciate your comments again and hope this response adequately addresses your concerns.

Response to “… explore the model’s generalization capabilities …”

To the best of our knowledge, prior constrained optimization methods for VRP have primarily focused on TSPTW, CVRPTW, and TSPDL. As summarized in the table below, our work is comparatively more comprehensive in its coverage of these variants:

If we apply the ICO method to problems beyond VRP or even combinatorial optimization, extensive domain-specific adaptations are necessarily required. However, the core idea of instance-level multiplier formulation is inherently general and may be applicable to other settings. In any RL scenario that requires both constraint satisfaction and generalization across instances, the limitations of policy-level multipliers also apply, making ICO a potentially valuable solution. We sincerely appreciate your comments again and hope this response adequately addresses your concerns.

Response to “Comparison with PIP-D”

Thank you for your thoughtful feedback. As noted in lines 260–261, “For TSPTW (DL) 100, we report the results of the models with the PIP decoder”, we adopt the PIP decoder (PIP-D) for TSPTW (DL) 100. Based on the results of PIP's paper, which show that PIP-D improves performance on $N=100$ datasets, but the original PIP has better results on $N=50$ datasets, we report results using PIP on $N=50$ and PIP-D on $N=100$ to reflect the best performance of PIP models. For simplicity, we refer to both variants under the unified “PIP” in our paper. We are sorry for this confusion, and will revise to make it clearer.

Response to “Training efficiency”

Thanks for your valuable question. First, we want to clarify that the training times of the PIP method and the proposed ICO method over 110k epochs are approximately the same: for example, around 60 hours for TSPTW50 and about 10 days for TSPTW100. At first glance, fine-tuning $\lambda$ appears computationally intensive. However, in our implementation, we mitigate this by using a fixed number of batches, and in each batch, only the feasible instances are replaced with new ones, as described in lines 216-217. That is, if there is an increasing number of infeasible instances requiring iterative updates in the current batch, the number of newly generated instances in future batches will decrease correspondingly. As a result, the total number of network forward and backward computations remains equivalent to that of the original PIP method.

Additionally, ICO's training metrics don’t directly reflect iterative inference, making the sample efficiency hard to evaluate during training. Instead, we compare methods under aligned training budgets, as we did in Tables 1 and 2.

In response to Point 1, we conducted new experiments using fixed $\lambda$ to train our model. The results show that using a fixed $\lambda$ in our model yields no difference from the baseline under the same training time.

Fixed $\lambda$ results on TSPTW50

Regarding Points 2 and 3, please refer to the results of PIP (dynamic $\lambda$) in Tables 1 and 2 of our paper. PIP (dynamic $\lambda$) applies subgradient ascent to adjust the single $\lambda$, serving as an advanced form of the “multiple $\lambda$” model you suggested. The results in Tables 1 and 2 show that our ICO method consistently outperforms this dynamic version, highlighting the effectiveness of instance-level $\lambda$ adaptation.

Response to “Generalization during inference”

Good point! Empirically, ICO generalizes reasonably well across varying $\lambda$ values. During training, the sampled or updated $\lambda$ values roughly range from 0.1 to 2.0. At test time, ICO handles $\lambda$ up to 5.0 for most instances, and up to 10.0 for some with large violations, showing robustness to unseen values. However, when $\lambda$ becomes excessively large or small (e.g., 0.0001), model performance may degrade or even collapse. While improving this aspect may further enhance performance, the current model’s generalization ability has already been sufficient to effectively optimize most instances.

---

We hope that our response has addressed your concerns, but if we missed anything, please let us know.

Thanks for dedicating your time to reviewing our paper! Your suggestions are very constructive for us to further improve the paper. Please find our detailed response below.

Response to “... does not seem to demonstrate generality for different models... ”

Thank you for your insightful and constructive feedback. Although our primary experiments are conducted based on the PIP backbone, we would like to clarify that the proposed ICO framework is inherently general and not restricted to any specific model architecture. In fact, it can be naturally extended to many backbone models within the domain of neural combinatorial optimization, as long as these models can be trained via reinforcement learning (RL) and Lagrangian relaxation. When adapting our method, users can simply incorporate the multiplier-conditioned embedding into the input of any neural policy network and employ the sampled or iteratively updated instance-specific multipliers in the RL training pipeline.

In response to your valuable suggestion, we have conducted additional experiments using a recently proposed backbone: RELD [1], which is designed to enhance cross-instance generalization through an improved decoder and achieve impressive performance. Your recommendation of BQ and GOAL is reasonable, but their supervised training is not compatible with the Lagrangian-based method. Following the generalization setting of RELD, we trained both RELD and RELD + ICO on instances with node size $N \sim \mathcal{U}[40,70]$, and evaluated them on the larger TSPTW200-medium dataset and TSPLIB dataset.

Combined with RELD and generalization TSPTW200 (medium difficulty)

Combined with RELD and generalization to TSPLIB ($N\le 200$, medium difficulty)

These results show that RELD + ICO consistently improves feasibility and optimality over RELD, confirming the generality and effectiveness of our method. Importantly, in contrast to PIP—which involves computing a mask with cubic time complexity relative to the number of nodes—RELD + ICO circumvents this computational overhead in large-scale instances, achieving a substantial reduction in inference time (from 316s to 54s) while preserving high solution quality and ensuring 0% infeasibility.

We hope these additional results and clarifications address your concerns.

[1] Rethinking Light Decoder-based Solvers for Vehicle Routing Problems. ICLR 2025.

Response to “... only conducted under the hard difficulty level …” and “… experiments of ICO under the other two difficulty levels...”

Thank you very much for your constructive and insightful comments.

As evidenced in the experimental results reported by PIP [2] (see Table 1 and Table 2), the infeasibility rates at the instance level on the easy datasets are already 0%, and those on the medium datasets are below 1%, which indicate that existing neural solvers can already handle such cases with high effectiveness. Therefore, we only selected the hard datasets in our experiments.

Nevertheless, we acknowledge that assessing performance across a broader spectrum of difficulty levels is also valuable. In response to your suggestion, we have conducted additional experiments on medium-level datasets to further examine the effectiveness of our method, as presented below. Experiments on easy datasets are not reported since all the compared neural solvers achieve 0% infeasibility. To make a distinguishable comparison, we used the original POMO as the backbone, instead of PIP.

TSPTW50 (Medium Difficulty)

TSPDL50 (Medium Difficulty)

We can observe that ICO consistently achieves significantly lower infeasibility rates and higher HV scores compared to POMO across medium-level datasets. Notably, in the TSPDL50 medium dataset, ICO reduces the infeasibility rate from over 11% (POMO) to just 0.19% when using T = 16, which further highlights the effectiveness of our method. We will revise our paper to include these new results and analysis.

Response to “... the experimental section lacks clarity in certain areas...”

Thank you for your valuable feedback. We respectfully clarify that the experimental settings in our paper are, to our understanding, adequately described. Many details are provided in Section 4.1, Appendix E, and in our released code. Reviewer dvDR has explicitly acknowledged the sufficiency of our provided experimental details. As for your specific concern on $\lambda$ settings, we describe the $\lambda$ configurations of PIP in Section 4.1 (lines 261–264), including $\lambda = 0.5$, $1.0$, $2.0$, and a dynamic variant, which is also clearly presented in Table 1. If any other part of the experimental setup remains unclear, please let us know. We’re happy to provide further clarification.

Response to “... there is no theoretical guarantee or proof of its effectiveness...”

Thank you very much for your insightful and constructive feedback. To the best of our knowledge, rigorous theoretical analysis for neural combinatorial optimization methods is still an open and challenging problem in the area. Consequently, a direct theoretical comparison is almost infeasible.

However, we are able to provide a simple justification for our proposed instance-level Lagrangian formulation. Let us define the policy-level objective as $F(\theta,\lambda) =\sum_{i=1}^N\left[ J(\pi_\theta, I_i) +\lambda\cdot J_C(\pi_\theta, I_i)\right]$ and the instance-level objective as $G(\theta,\{\lambda_i\}) =\sum_{i=1}^N\left[ J(\pi_\theta, I_i) +\lambda_i\cdot J_C(\pi_\theta, I_i)\right]$, then we have the following inequality:

$\min_{\{\lambda_i \geq 0\}} \max_\theta G(\theta, \{\lambda_i\}) \leq \min_{\lambda_1=\cdots=\lambda_N =\lambda} \max_\theta G(\theta, \{\lambda_i\})=\min_{\lambda \geq 0} \max_\theta F(\theta, \lambda)$

This result clearly demonstrates that the proposed instance-level formulation is guaranteed to be no worse than the conventional policy-level formulation. Moreover, it also implies that the greater the heterogeneity among the optimal multipliers ${\lambda_i}$, the more expressive power and potential benefit the instance-level formulation is likely to offer.

We hope this clarification helps to address your concern, and we are grateful again for your valuable feedback. In the future, we will put more efforts in theoretical analysis of NCO methods, to fill in the gap in the area.

Response to “... uses the instance infeasibility rate but does not consider the solution infeasibility rate.”

Thank you for your insightful comment. The instance-level infeasibility rate measures the fraction of problem instances with no feasible solution found, directly reflecting the method’s ability to satisfy constraints. In contrast, the solution-level rate counts the proportion of infeasible solutions overall. While useful in some cases, it may be misleading here, as it depends heavily on the distribution: easy instances may yield many feasible solutions, while hard ones may yield none. This can lead to a deceptively low solution-level rate even when the method fails on harder instances. Given this, we believe the instance-level rate offers a more meaningful and reliable metric for evaluating constraint satisfaction in our study. We will revise to add some discussion to make it clearer. Thank you.

Response to “Can ICO be applied to other algorithms based on Lagrange multipliers?”

Thank you very much for your insightful question. We believe your question can be understood from two perspectives:

1. Whether ICO can be integrated with other algorithms that optimize Lagrange multipliers;
2. Whether ICO can be applied to Lagrangian-based methods in broader domains.

Both interpretations raise important and interesting directions for exploration. Regarding the first perspective, ICO is indeed compatible with various Lagrangian multiplier algorithms. For instance, it can be combined with PID control-based approaches, as discussed in Appendix F.2. For the second, we believe ICO has potential in other RL domains requiring constraint satisfaction and cross-instance generalization. In such settings, the limitations associated with policy-level multipliers also exist, making ICO a potentially valuable solution.

Response to “How does the training time of ICO compare to PIP?”

Thanks for your valuable question. The training times of the PIP method and the proposed ICO method over 110k epochs are approximately the same: for example, around 60 hours for TSPTW50 and about 10 days for TSPTW100. At first glance, fine-tuning $\lambda$ appears computationally intensive. However, in our implementation, we control the number of forward and backward passes by reducing the new instances at the fine-tuning stage, ensuring that the overall training cost remains similar.

---

We hope that our response has addressed your concerns, but if we missed anything, please let us know.

Thanks for dedicating your time to reviewing our paper! Your suggestions are very constructive for us to further improve the paper. Please find our detailed response below.

Response to “… the update of $\lambda$ can only increase $\lambda$ …”

Thank you very much for your insightful comment. We truly appreciate your suggestion, which has prompted us to further refine our method.

As you pointed out, our original implementation employs subgradient ascent (SGA) to update the Lagrange multiplier $\lambda$ during the training phase. While this approach is relatively straightforward, it is also widely adopted in constrained optimization literature and has theoretical convergence guarantees under appropriate learning rate settings. In our experiments on TSPTW and TSPDL, SGA with a carefully tuned learning rate has been effective in guiding $\lambda$ towards values that yield feasible solutions. In our early-stage attempts, we compared Proportional-Integral-Derivative (PID) control with SGA at inference using the same pre-trained policy (trained without iterative $\lambda$ updates). We observed that PID did not consistently outperform SGA in inference. Therefore, we chose the more straightforward SGA strategy as the final implementation.

However, we acknowledge your concern regarding the non-decreasing nature of SGA, which may indeed lead to suboptimal results, especially in combinatorial settings where a fixed learning rate may cause the optima to be skipped. Motivated by your feedback, we have conducted additional experiments to explore more flexible update rules, integrating them not only into inference but also into the training phase.

Specifically, we have explored the following variants:

1. Full PID control: We incorporated PID control into the training phase.
2. ID control (without the proportional term): Considering the non-smooth nature of combinatorial problems, the proportional term in PID may be over-aggressive. Hence, we removed it and adopted an Integral-Derivative (ID) control method.

Below are the experimental results for TSPTW50-hard and TSPDL50-hard, where the normalized HyperVolume (HV) is computed based on the reference point (5%, 5%):

TSPTW50-hard

TSPDL50-hard

The experimental results show that the PID and ID controls consistently offer improvements over the original SGA method. In particular, ID control achieves the highest HV scores on both benchmarks. We will revise the paper to include these findings. Thank you again for your valuable feedback.

Response to “... still requires adaptive tuning of $\lambda$ for each problem instance...”

Thank you very much for this insightful comment. First, we would like to emphasize that although our proposed method involves instance-specific tuning of the multiplier $\lambda$, the increased overhead during training and inference is relatively small. As demonstrated in Table 2, our method can achieve superior performance to the PIP baseline with only two iterations at the inference stage, where the additional overhead is affordable. During training, we control the number of forward and backward passes to match that of the baseline methods by reducing the training instances at the fine-tuning stage, ensuring that the overall training cost remains similar.

We fully agree that training a predictor to estimate a near-optimal $\lambda$ for each instance is a promising direction. In response to your valuable suggestions, we have explored this idea by training a network to distinguish the hard instances requiring high $\lambda$ values. This network makes classification based on instance-level features, i.e., all node features. Since most instances can be directly solved by our ICO policy without iterations, the positive and negative samples are extremely imbalanced. To address this issue, the focal loss [1] is applied to adaptively assign the weights of each sample.

We collect 100k instances and labels of TSPTW50 to train the classifier for 50 epochs. However, the resulting prediction error was prohibitively high: the classifier only has 12% recall in identifying the hard instances, which is far from deployment. We hypothesize that this is due to the limited expressiveness of instance features. Note that the instances are drawn from a single distribution and possess similar constraint characteristics, making them difficult to distinguish in terms of constraint hardness.

Nevertheless, your comment has inspired us to consider a new method beyond static prediction. Specifically, since the rollout process in our model is sequential rather than one-shot, it is possible to dynamically adapt the value of $\lambda$ during the solution construction process. We are currently investigating a strategy that leverages partial solution information—such as constraint tightness and action entropy observed in earlier decision steps—to guide the adjustment of $\lambda$ in later steps. This approach could enable a more effective initialization of $\lambda$ in the first iteration, and has the possibility to be integrated into the RL paradigm, as you suggested.

We sincerely apologize for not being able to complete this experiment within the limited timeframe of the current author response phase. We greatly appreciate your insightful suggestion, and will make our best effort to include the corresponding experimental results in the next discussion phase.

[1] Focal Loss for Dense Object Detection. TPAMI 2020.

Response to “... the number of timeout nodes...”

Thank you for your thoughtful comment. In the methodology section of our paper, we assume TSPTW as the example problem to illustrate our approach. In this context, “timeout nodes” refer to those violating time window constraints. We sincerely apologize for its ambiguity and will revise to clarify this definition. Regarding the inclusion of this term in the reward, this design choice is based on empirical findings from prior work (i.e., PIP), where minimizing this heuristic penalty enhances constraint satisfaction. To ensure a fair and consistent comparison, we follow the same reward structure in our implementation. We will make the necessary revisions to explain this aspect.

Response to “... more guidance on how the random distribution of $\lambda$ values should be selected...”

Thank you for your thoughtful comment. Our guiding principle in selecting the distribution of $\lambda$ is to align it with the empirical frequency of constraint violations. In our experiments, we observed that the trained policy often leads to small violations, resulting in a long-tailed distribution (see Appendix F.5). Thus, we adopted a triangular distribution that emphasizes smaller $\lambda$ values, better matching the empirical structure. This principle is potentially generalizable, as such statistics are easy to obtain in most cases. We hope this explanation addresses your concern. Thank you again for your valuable feedback.

Response to “... CVRPTW and CVRPDL may have limited number of vehicles...”

Thank you for your insightful comment. We agree that in many applications, CVRPTW and CVRPDL often involve a limited number of vehicles, where constraint violations cannot be resolved by simply adding vehicles. Our original statement was based on the common experimental setting, assuming unlimited vehicles, and our intention is to highlight the relative difficulty of constraints in TSPTW and TSPDL. We will revise the paper to rectify this statement.

Besides, we also evaluate CVRPTW under a limited fleet size in Appendix F.1. Our ICO method still outperforms baselines in this harder setting, further demonstrating its effectiveness and generality.

Response to “Is there a reason for using REINFORCE instead of more advanced algorithms, such as PPO?”

Thank you very much for your insightful question. To the best of our knowledge, earlier works in neural combinatorial optimization [1, 2] have indeed explored actor-critic algorithms such as PPO, following the prevailing practices within the RL community. However, a subsequent seminal study [3] reported that, somewhat counterintuitively, these actor-critic methods tend to underperform compared to the classical REINFORCE algorithm in this specific context (see Table 1 and Figure 3 in [3]).

However, the mechanisms behind these observations remain an open, theoretically unvalidated question. One plausible explanation for this phenomenon is the inherent difficulty of training a reliable critic in high-dimensional combinatorial state-action spaces. The complexity of the solution space may hinder the critic's ability to provide accurate value estimates. In contrast, REINFORCE—being a critic-free method—relies directly on the observed objective values to compute policy gradients. This can allow for more accurate advantage estimation, thereby leading to superior performance in combinatorial optimization tasks.

We hope this clarifies the rationale behind the choice of REINFORCE in this setting and truly appreciate your question and the opportunity to discuss this further.

[1] Neural Combinatorial Optimization with Reinforcement Learning. ICLR 2017.

[2] Reinforcement Learning for Solving the Vehicle Routing Problem. NeurIPS 2018.

[3] Attention, Learn to Solve Routing Problems! ICLR 2019.

---

We hope that our response has addressed your concerns, but if we missed anything, please let us know.