Learning to Handle Complex Constraints  for Vehicle Routing Problems
Authors: Jieyi Bi
Yining Ma
Jianan Zhou
Wen Song
Zhiguang Cao
Yaoxin Wu
Jie Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: vehicle routing problem
learning to optimize
constraint handling
Primary area: optimization
TL;DR: We propose generic and effective Proactive Infeasibility Prevention (PIP) frameworks to advance the capabilities of neural methods towards more complex VRPs.

Abstract: Vehicle Routing Problems (VRPs) can model many real-world scenarios and often involve complex constraints. While recent neural methods excel in constructing solutions based on feasibility masking, they struggle with handling complex constraints, especially when obtaining the masking itself is NP-hard. In this paper, we propose a novel Proactive Infeasibility Prevention (PIP) framework to advance the capabilities of neural methods towards more complex VRPs. Our PIP integrates the Lagrangian multiplier as a basis to enhance constraint awareness and introduces preventative infeasibility masking to proactively steer the solution construction process. Moreover, we present PIP-D, which employs an auxiliary decoder and two adaptive strategies to learn and predict these tailored masks, potentially enhancing performance while significantly reducing computational costs during training. To verify our PIP designs, we conduct extensive experiments on the highly challenging Traveling Salesman Problem with Time Window (TSPTW), and TSP with Draft Limit (TSPDL) variants under different constraint hardness levels. Notably, our PIP is generic to boost many neural methods, and exhibits both a significant reduction in infeasible rate and a substantial improvement in solution quality.

Learning to Handle Complex Constraints for Vehicle Routing Problems
Jieyi Bi', Yining Ma Jianan Zhou', Wen Song", Zhiguang Cao², Yaoxin Wu Jie Zhang!
1 Nanyang Technological University
Shandong University
Singapore Management University
Findhoven University of Technology
jieyi001@e. ntu. edu. ag, yiningmaCu. nus edu, j jianan004Ge.o .nt. edu..aduus wensongdemail. sdu edu. zgcao@smu. edw.e/mmueede......... sg, wu2@tue nl, zhangj @untu. edu. sg
Abstract
Vehicle Routing Problems (VRPs) can model many real-world scenarios and often involve complex constraints. While recent neural methods excel constructing solutions based on feasibility masking, they struggle with handling complex con- straints, especially when obtaining the masking itself is NP-hard. In this paper, we propose novel Proactive Infeasibility Prevention (PIP) framework to advance the capabiliiiies of neural methods towards more complex VRPs. Our PIP integrates the Lagrangian multiplier as a basis to enhance constraint awareness and introduces preventative infeasibility masking to proactively steer the solution construction process. Moreover, we present PIP-D) which employs an auxiliary decoder and two adaptive strategies learn and predict these tailored masks, potentially enhaneing performance while significantly reducing computational costs during training. To verify our PIP designs, we conduct extensive experiments on the highly challenging Traveling Salesman Problem with Time Window (TSPTW), and TSP with Draft Limit (TSPDL) variants under different constraint hardness levels. Notably, our PIP is generic boost many neural methods, and exhibits both a significant reduction in infeasible rate and substantial improvement in solution quality.
Introduction
Vehicle routing problems (VRPs) are NP-hard combinatorial optimization problems with complex constraints that model real-world scenarios, such logistics [1] and supply chains [2]. For decades, traditional solvers relied on hand-crafted rules for VRP optimization and constraint handling. Recently, the coaeninngtt-oppiniie
community [3] has successfully trained deep neural networks automatically construct VRP solutions in an end-to-end manner [4-6]. These data-driven neural methods offer greater efficiency and high parallelism for batch optimization, making them favorable alternatives.
In general, neural methods construct VRP solutions by autoregressively sampling a node from its predicted distribution while masking out nodes that would violate constraints to ensure the solution's 's fcasibility. Despite successes (c.g., on TSP and CVRP), this masking mechanism assumes that 1) the feasibility of the entire solution be properly decomposed into the fcasibility of each node selection
Yining Ma is the corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

step, and 2) ground truth masks are easily obtainable for each step. However, such assumptions may fail in VRPs (e.g,, TSPTW) with complex interdependent constraints among decision variables (i.e., nodes). As will be discussed in Section 4.1, this creates a masking dilemma- considering only the local feasibility of node selections does not guarantee the overall feasibility of the constructed solutions, while computing global feasibility masks that account for future impacts transforms masking itself into another intractable NP-hard problem.
These observations highlight significant gaps in applying recent neural methods to practical VRPs, necessitating research on new constraint-handlinn frameworks. In the literature, few studies have focused on novel ways of handling feasibility in neural constructive solvers. Although preliminary methods have attempted to mitigate it by relaxing constraints into soft ones [7, 8] or supplementing networks with more feasibility-relan -eelate features [9]. the former is prone to failure when applied to more complex scenarios, while the latter requires problem-specifie features and a large supervised learning dataset, limiting its adaptability to broader VRPs. Consequently, neural methods still show limited flexibility, poor feasibility rates and large optimality gaps in solving those complex VRPs.
In this paper, we propose novel Proactive Infeasibility Prevention (PIP) framework to extend the capabilities of neural constructive methods for VRPs with complex interdependent constraints. Our PIP first integrates the Lagrangian multiplier method into the reinforcement learning framework of neural methods, promoting initial constraint awareness and search guidance. To further address the limitations of the Lagrangian multiplier method on complex constraints, we then introduce preventative infeasibility masking to proactively steer the search to (near- (eea--)ee regions during solution construction. By doing so, PIP significantly enhances feasibility rates and reduces optimality gaps. Moreover, to reduce the costs of obtaining preventative infeasibility information during training, we present PIP-D, which employs an auxiliary decoder to learn and predict masking information. Our PIP-D also incorporates two adaptive strategies: one to balance infeasible and feasible masking information for different problem hardness, and another to periodically update the model so to balance training efficiency with prediction accuracy. These advancements enable PIP-D to achieve comparable or even better performance than PIP, particularly on larger and more constrained VRP instances, while significantly reducing computational complexity.
Our contributions are as follows: 1) Conceptually, we represent an early work to address and advance the handling of complex interdependent constraints in VRPs, where the original masking loses effec- tiveness due to the aforementioned dilemma, thereby extending the applications of neural methods to more practical scenarios. 2) Methodologically, we propose novel PIP and PIP-D approaches that can boost the capabilities of most constructive neural methods. Specifically, we leverage the Lagrangian multiplier method and introduce preventative infeasibility masking, which is further learned by an auxiliary decoder network with two adaptive strategies, to proactively and efficiently steer the search during solution construction. 3) Experimentully, we conduct extensive validation to demonstrate the effectiveness and versatility of PIP across various backbone models (i.e., AM [4], POMO [5]. and GFACS [10]) and complex VRP variants (i.c., TSPTW and TSPDL). Notably, PIP achieves both significant (up to 93.52% reduction in infeasible rate and a substantial improvement in solution quality on synthetic and benchmark datasets with different constraint hardness levels.
2 Related work
Neural solvers for VRPs. Existing literature on learning to optimize VRPs features two primary paradigms: constructive solvers and iterative solvers. Constructive solvers learn policies to con- struct solutions from scratch in an end-to-end manner. Early works introduce Pointer Network to approximate the optimal solution to TSP [11, 12] and CVRP [13] in an autoregressive Among all AR solvers, the attention-base model (AM) [4] represents a milestone in solving a series of VRPs. Later, the policy optimization with multiple optima (POMO) [5] further improves upon AM by considering the symmetry property of VRP solutions. Numerous recent studies have then aimed to further enhance their performance [14-23] and versatility [24-27]. Besides the AR methods, several works construct a heatmap. which indicates the probability distribution of each edge being part of the optimal solution, to solve VRPs in a aon-autoregressive (NAR) manner [10, 28 28-34]. Despite the superior performance on large-scale instances, we note that a recent work [35] questions the effectiveness of heatmap generative methods due to the misalignment of training and testing objectives. Differently, iterative solvers learn policies to iteratively refine an initial solution. The policies are often trained in contexts of classic heuristics meta-heuriste for obtaining more
(AR) way.

---

efficient and effective search components [36-45], Generally, constructive solvers can efficiently achieve desirable performance levels, whereas iterative solvers hold the potential to search for near- optimal solutions with a prolonged time budget. Additionally, there are also several works studying the scalability [46-52], generalization [53-58], and robustness [59, 60] of neural VRP solvers, and leveraging large language models (LLMS) to optimize VRPs [61-63].
Constraint handling for VRPs. Most neural methods for VRPs manage constraints using a feasibil- ity masking mechanism that eliminates actions leading to infeasible solutions during construction or iteration search [4, 28, 32, 41]. However, such mechanism assumes the availability of accurate masks and often lacks constraint awareness learning during training, which is not always practical or desirable. For example, Zhao et al. [64] highlighted the benefits of learning to modulate agent behaviours in the 3D Bin Packing Problem, and Ma et al. [45] showed that temporary constraint viola- tions could enhance neural iterative solvers. Despite their successes, these approaches are inherently unsuitable for assisting constructive solvers to address the VRPs with complex interdependent con- straints studied in this paper. While Tang et al. [8] and Zhang et al. [7] proposed methods to transform hard constraints into soft ones via relaxation techniques and problem redefinition, respectively, they may only be able to yield near-feasible solutions with large infeasible rates for VRPs with complex constraints. More recently, Chen et al. [9] developed multi-step look-ahead (MUSLA) method specifically tailored for TSPTW, incorporating problem-specife features and a large supervised learning dataset. In contrast, this paper proposes a more flexible and generic PIP framework based on novel ideas of preventative infeasibility masking, learnable decoders, and adaptive strategies to advance broader range of neural methods without needing labelled training data.
3 Preliminaries
In this paper, we mainly consider two VRP variants with complex interdependent constraints (i.e., TSPTW and TSPDL), and neural solvers (i.e., AM [4], POMO [5] and GFACS [10]).
Problem definitions and notations. A VRP instance can be defined over a complete graph G = {V,E), where V = {vo, u,,..., } denotes the node set, and & = (vs, vy) [ea, 2/y E V, i o j} denotes the directed edge set among all nodes, The objective is to minimize the total cost (e.g. Euclidean length) of the solution tour. To form a feasible solution, each node in V should be visited exactly once while respecting problem-speciffe constraints. We consider two types of VRP constraints that are practical in industry: 1) Time window constraint: The arrival time at node Uy denoted as t,, must fall within a customer-specific time window [1; u.]. If The vehicle arrives early (i.e., 4 < 4,), it must wait until 4; 2) Drafi limit constraint: Each node ;; represents port with a non-negative demand óe and a maximum draft d; We denote the current cumulative load of the freighter at port 0; as ag in a given solution, which should not exceed the corresponding maximum draft d: of the port.
Constructive solvers for VRPs. Popular neural constructive solvers [4, 5] typically parameterize the policy using encoder-decoder model with parameter 0, trained with reinforcement learning (RL). Given a VRP instance 9 = (V,E}, the features of each node vn are represented as f = {a., Vi, ca). where T4. Y are node coordinates, c; represents time windows in TSPTW and c; = {ōr, } for demand and draft limits in TSPDL). The encoder transforms node features into high-dimensional representation embeddings h, which, combined with the context of the partial tour, represent the current state. The decoder takes them as inputs and outputs probabilities for candidate nodes (actions). The reward R(r(g) is the negative tour length. The policy Te is typically trained using REINFORCE [65] as follows:
related features (e.g.. G. [44, u, for
K
LR. (019)
1 K (R. - b(G) V log Te (7:19),
Σ
1
where K denotes the number of sampled solutions тą for a given training instance G, and b(-) is a baseline function to reduce the variance. Specifically, the baseline is the reward (negative tour length)
of the solution derived greedily in AM or the average reward of sampled solutions 1 EK R (T.19) ()) in POMO. Notably, POMO stipulates the starting node of each solution for diversification, which, however, may hinder solution feasibility in our studied complex constrained problems. Based on our preliminary experiments, POMO with and without diverse starting nodes achieve around 50.700 70% and 1.75% infeasible rates on the easy TSPTW-50 datasets, respectively. Therefore, we remove the starting node stipulation in POMO and instead sample n solutions to calculate the baseline.
K
3

---

Iraddingg
Line Wandon
Visted biae (hezabicl
Vinted Edge (inionNe))
Anumal (loccaitle)
Amnal (Tiocti))
Armoll Time (bsfoee))
Antened Amtal
Unssoled Node
Vaite Neda
OUNEIES MM
CUABLRO
Partial solution
Feasible solution
Infeasible solution
Figure A TSPTW instance illustrate the malfunction of existing masking mechanism (left three panels) and NP-hardness of obtaining precise infeasible masks (right panel). The orange bar represents the time window [4, u.] for node v,. For the partial solution Up - vı. both 0o and vg locally feasible. However, selecting results in the irreversible infeasibility of U/ afterwards.
4 Methodology
We now discuss the limitations of existing masking mechanisms in solving VRPs with complex interdependent constraints, followed by a detailed introduction of our PIP and PIP-D) frameworks.
4.1 Dilemma of feasibility masking
The core of feasibility masking in neural constructive solvers is to filter out invalid actions that violate constraints, based on the assumption that the global feasibility can be decomposed into the feasibility of each node selection step. and that ground truth masks are obtainable for each step. Without loss of generality, we illustrate the dilemma of feasibility masking using a TSPTW example. In TSPTW, nodes are masked out if they have been visited or cannot be visited before their time window closes. However, the feasibility of selecting a node at a particular step impacts the current time, thereby affecting all future selections due to the interdependence of time window constraints. Thus, considering only local feasibility does not guarantee overall feasibility and may lead to irreversible infeasibility. For instance, in 4-node TSPTW instance with time windows {10, 7, [1, 4], [2, [2, 6]} as illustrated in the left panel of Figure 1, there a feasible solution 7 (Vo + 02 + U2 + 0z). Yet, with the partial solution to 21. both U/ and Uty appear locally feasible. If the solver selects us, the tour becomes infeasible irreversibly. A potential remedy is to compute global feasibility masks that consider all future possibilities, as illustrated in the right panel of Figure 1. However, this makes masking itself an NP-hard problem, which creates a dilemma between ensuring solution feasibility and managing computational complexity. Note that this dilemma less critical in CVRPTW. which involves multiple vehicles and routes, providing more flexibility. If one route becomes infeasible, another vehicle departing at time can cover the missed nodes, reducing the impact of constraint interdependencies. However, this issue is severe in TSPTW and other variants like TSPDL.
4.2 Guided policy search by PIP
We first formulate the solution construction process of VRP as Constrained MDP (CMDP) defined by the tuple (S, A, ,,, R. C), where S is the state space, AA is the action space that travels from node i to node U/ R : S x A x S is the reward function, C S x A x S is the constraint violation cost x + [0, 1] is the transition probability function. At each time step, the neural solver outputs the probability of all candidate nodes, and selects one to construct complete solution т. The objective of CMDP is to learn a policy ne : P(A) that maximizes the summation of the state-wa state-wise reward subject to certain constraints,
(penalty) function, and P : S
max [(TO) = ET
R (vr, ((VENN))ET
Σ
s.l. To E Hr, --= = {Ir E IT (T) Km, Vm E M}}
where J is the expected return of the policy, T denotes the set of all feasible policies, Kmn represents the boundary of the inequality constraints Cm. and M is the number of constraints. Specifically,

---

me:
Ro sto
Boy
ng Mon
Rdx
Fle
y
F
11;
(n)
(b)
(d)
(E)
Figure 2: Illustration of policy optimization trajectories on VRP with varying difficulty levels (a)(b)(d casy and (c)(e) hard, and different constraint handling schemes (a) feasibility masking, (b)(c) Lagrangian multiplier, and (d)() our PIP. The orange-filled circle denotes the feasible policy space Hp, while the dotted frame represents the actual search space of the neural policies TT.
feasible policy и is one whose expected value constraint violation w.r.t Cm. denoted as Te.. (T), does not exceed Km. Note that Km is set to 0 throughout this paper since consider the hard constraints that do not tolerate any violation. Moreover, we set the reward function R to the negative value of the Euclidean distance between two nodes, i.e., (e (v;, 0;)) -| Uyl/2-
By applying feasibility masking, the search is confined to only feasible regions, allowing neural methods to focus solely on the objective function in Eq. (2) without explicitly considering constraint awareness or constraint violations. However, these methods lose effectiveness when such masks are unavailable, leading inefficient searches in large infeasible regions. To address this, propose PIP, combining Lagrangian multiplier for constraint awareness and preventative infeasibility masking to confine the search space feasibee regions for complex constrained problems.
Lagrangian-assise constraint awareness. We design a Lagrangian multiplier based method to incorporate constraints C' into the reward function R. Based on the Lagrangian Multiplier Theorem, CMDP formulation Eq. (2) transformed into following MDP formulation for VRPs:
M
min max L(X,0) = min max - ETTaT A20 0
Σ
- 1512+
Σ AmJc Jom (T) + JIN m==1
(3)
X
where L is the Lagrangian function, and Am is non-negative Lagrangian multiplier. Generally, the constraint violation term is calculated the total violation value of all constraints. In TSPTW, (Tw(T) = Σi=o max(4; ue, 0), and in TSPDL, (TI.(T) Ei= max(o; di, 0). Additionally, we introduce the number of infeasible nodes in the solution т, termed as JIN. as an extra term in the Lagrangian function for better constraint awareness, which is empirically found to be effective reduce the infeasibility rate. While Lagrangian relaxation has been explored neural iterative methods for soft objectives [8], our approach introduces a distinct constraint violation cost function tailored for neural constructive methods and considers fixing the Lagrangian multiplier (the dual variable) and optimizing the primal variable 6, significantly reducing computational overheads.
Preventative infeasibility (PI) masking. As depicted in Figure 2(b), the customized Lagrangian multiplier guides the neural policy towards a potentially feasible and high-quality space using Eq. (3). However, for more complex cases shown in Figure 2(c), neural solvers may still struggle navigate the large search space. To further improve training efficiency and solution feasibility, we introduce preventative infeasibility (PI) masking proactively avoid selecting infeasible nodes during the solution construction process. As shown in the left panel of Figure 3, if selecting a candidate node (i.c., orange node) results any remaining candidates (i.e., green node) becoming potentially unvisitable in the next step due to constraint violations, it is marked as infeasible (i.e., red node) since selecting would cause irreversible future infeasibility (see Appendix A.3 for a detailed example). Note that we employ simple yet effective one-step PI masking in this paper to balance computational costs without iterating over future possibilities (which is NP-hard). Together with the customized Lagrangian multiplier, our PIP proactively reduces the search space to near-feasible domain II p. as shown in Figures 2(d)-(e). Notably, such PIP design is generic and can applied enhance most neural constructive solvers for VRPs with complex interdependent constraints.
5

---

Lavisited Node
Visited Node
Assumed Visited Node Tessible Edge
Potesnaal Infeasible Node Infeasible Edge
Predicted Indeasible Nods
Node Embedding
Visited Edge
Assumed Visited Edge
Input
Ourput
Method
OI
PIP Deceder
Assusee Stop
Encoder
Node Embeddding
Sampler
Loss
Node Feuture
Prodiction
Loop
RL
Partial Solution
Roating Decuder
ol Probabilities
Solution Feature
Solation Embedding
21
PIP Method
Labels
P1 Extimater
LOSA
Prevetsaivv Infeasbiity Fxtmater
Sumpler
Figure 3: An illustrative overview our proposed approach: Left Preventative infeasibility (PI) estimator. Right - PIP (highlighted in green) framework and PIP-D (highlighted in blue) framework.
4.3 Learning to prevent infeasibility
Benefiting from the constraint-awar optimization guided by our PIP. neural methods gain enhanced capabilities to address complex constraints, significantly boosting feasibility and optimality. However, acquiring the above PI information introduces extra computational costs (see Section 5). To alleviate this, we propose an auxiliary decoder network to learn and predict these masks, replacing the time- consuming process of generating PI information with a much faster forward pass of the PIP decoder. This further accelerates the training process, resulting in enhanced version of our PIP framework, termed PIP-D. The overall framework of PIP-D illustrated Figure 3.
Auxiliary PIP decoder. As presented in Figure 3, we incorporate an auxiliary decoder to learn and predict the PI masks. Our PIP-D simultaneously involves training routing decoder (the original one) that maximizes the expected reward of solutions in Eq. (3) and PIP decoder that minimizes the prediction error on the PI masking using a weighted binary cross-entropy loss. The combined loss function is weighted sum of these two objectives, i.e., L = aLRL + LLP.. To ensure the generality, the PIP decoder mirrors the architecture of the backbone model and only adjusts the final output layer with Sigmoid activation. More details of our PIP decoder are provided in Appendix B.
PIP-D training with adaptive strategies. Nevertheless, efficiently training the PIP decoder together with the routing decoder necessitates effective designs. We address this with two adaptive strategies. Firstly, training the PIP decoder at every gradient step would result in higher computational complexity than the original PIP, counteracting our goal of reducing training complexity. Hence, we adopt periodic update strategy that intermiltently updates the PIP decoder instead of continuously doing so. This approach is based on the observation that the PI masks recommended by the neural network tend to remain robust over short training periods. Specifically, we first train the PIP decoder with E epochs, then periodically update E, epochs per Ep epochs, and finally conduct Ei-epoch updates. In this way, the computational costs are reduced and can be adaptively adjusted. Secondly, we consider balancing feasible and infeasible PI signals for instances with different inherent hardness. Given that the proportion of signals identified for feasible and infeasible nodes can vary significantly across different VRP variants with different inherent hardness, we employ a weighted balancing strategy to mitigate the influence of label imbalance [66], which formulated follows:
T Σ V Cpp (0|g)- = T
(Winfss g. V log (po (g:)) + Wpa (1 (1-g)) V V (1 Po (9.))): (4)
where T is the total decoding step to construct a complete solution. The weights of each category are caleulated by their corresponding sample number, i.e, Winfab Not. Was Nue where 2NNii
2N
Ninta and NED are the number of infeasible and feasible nodes identified by our PI masking (g:)
in specific decoding step I, respectively. Moreover, beyond the above two critical strategies, we explore additional strategies to accelerate the training of the PIP decoder, including fine-tuning and carly-stopping techniques, which are discussed in Appendix D.3.

---

Table Experiments on TSPTW instance with three different hardness
50
100
Method
Infeasible & Inst.
Infeasible %
Sol.,
Obj.
Gap
Time.
Sol.
Inst.]
Obj.
Gap.
Time!
LKH3
0.00%
0.00%
7.31
0.00%
4.6h
0.00%
0.00%
10.21
0.00%
8,5h
ORTools
0.00%
0.00%
7.34
0.96%
7h
0.00%
0.00%
10:41
1.97%
14h
Greedy-L.
100.00%
100.00%
13.8s
100.00%
100.00%
1.3m
Greedy-C
0.00%
0.00%
26.08
257. 27%
4.5s
0.00%
0.00%
52.14
411.13%
12s
JAMPR #
0.00%
249.03%
1.2m
100.00%
1.6m
OSLA
1180%
8.15%
15.6s
MUSLA #
8,20%
7.32%
1.3m
18.60 18.60%
14.6%
9.8m
MUSLA adapt
0.10%
5.63%
0.60%
12.01%
1.1h
Easy
AM
100.00%
100.00%
Sm
100.00%
100.00%
21m
AM
3.46%
0.22%
8.02
9.82%
5.2mn
7.87%
1.49%
11.84
16.07%
21m
AM*+PIP
0.55%
0.00%
7.87
7.67%
10.7m
0.45%
0.00%
11.42
11.86%
1h
AM*+PIP-D
0.51%
0.00%
7.91
8.19%
11m
0.25%
0.00%
11.53
13.02%
1h
POMO
100.00%
100.00%
100.00%
100.00%
21s
POMO*
1.75%
0.00%
7.54
3.08%
13s
2.11%
0.00%
10.83
6.07%
21s
POMO
0.32%
0.00%
7.50
0.00%
10.57
3.53%
48s
POMO" PIP-D
0,28%
0.00%
7.49
2.51%
15s
0.06%
0,00%
10.66
4,39%
48%
LKH3
0.00%
0.00%
13:02
0.00%
0.00%
0.00%
18.74
0.00%
10.8h
ORTouls
15.77%
15.77%
13.02
0.30%
5.9h
0.52%
0.52%
19.34
3.23%
13.8h
Greedy-L
100.00%
100.00%
100.00%
100.00 00%
Greedy-C
47.52%
47.52%
25.33
96.43%
4.2s
20.34%
20.34%
51.62
176.07%
11.4s
Mediun
AM
100.00%
100.00%
5m
100.00%
100.00%
21m
AM
24.84%
0.27%
13.81
6.11%
50.19%
0.09%
21.42
14.34%
21m
PM*
7.62%
0.35%
13.68
5.06%
11m
12.73%
0.04%
20.57
9.82%
1h
AM*+PIP-D
11.96%
0.33%
13.65
4.87%
8.80%
0.02%
20.80
11.03%
POMO
100.00%
100.00%%
13s
100.00%
100.00%
/
218
POMO*
3.77%
5.23%
18.77%
0.12%
10.93%
POMO* + PIP
4.53%
0.90%
13.40
2.91%
15s
3.88%
0,19%
19.61
4.65%
486
POMO" + PIP-D
3.83%
0.65%
13.45
3.32%
15s
3.34%
0.03%
19.79
5.64%
48s
LKH3
0.12%
0.12%
25.61
0,00%
7h
0.07%
0.07%
51.24
0.00%
1.4d
ORTools
65.72%
65.72%
25.76
89.07%
89.07%
51.61
0.00% /
Greedy-L
100.00%
100.00%
21.8s
100.00%
000.
1.3m
Greedy
72.55%
72.55%
93.38%
93.38%
1.43%
Hard
AM
100.00%
100.009%
5m
100.00%
100.00%
21m
AM
39.87%
18. 88%
26.08
1.425%
5m
100.00%
100.00%
21m
AM*+PIP
18.07%
1.98%
25.71
0.38%
41.92%
16.46%
$1.49
0.47%
1h
AM*+PIP-D
30.39%
4,40%
25.80
0.67%
11m
53.09%
5.33%
51.55
0.57%
1h
POMO
100.00%
100.00%
13s
100.00%
100.00 100.00%
21s
POMO*
39.26%
35.25%
26.22
1.61%
13s
100.00%
000
21s
POMO" PIP
5.54%
2.67%
25.
0.18%
15s
31.49%
16.27%
51.42
0.37%
48s
POMO PIP-D
6.76%
3.07%
25.69
0.28%
15s
13.18%
6.48%
$1.39
0.31%
48s
Results are adopted from [9] due to unavailable source code, with our 'Easy" settings correpondinng to their 'Mediam' dataset. available due feusible solutions
The corresponding results
given 19].
We report the average results for instances where feusible solutions were found, which vary across different models. Despite these variations, the results for overlapping feasible instances consistcatly show similar patterns (sce Appendix D.2).
Experiments
In this paper, we propose a Proactive Infeasibility Prevention (PIP) framework and its enhanced version, PIP-D, to address the limitations of existing masking mechanisms for handling complex con- straints. Notably, our PIP and PIP-D are generic and can be applied to boost various problem variants and neural methods. To evaluate the effectiveness our method, we apply our PIP frameworks to two representative AR constructive methods, AM [4] and POMO [5], and the latest NAR constructive GFACS [10]. For the benchmark problem, we consider two representative complex VRP variants with strong interdependent constraints that challenge existing neural methods (i.c.. TSPTW and TSPDL, each at varying levels of hardness) with small problem scale n = 50, 100 for AM [4] and POMO [5] and large scale 500 for GFACS [10]. All the experiments are conducted on servers with NVIDIA GeForce RTX 3090 GPUs and Intel(R) Xeon(R) Gold 6326 CPU at 2. Our implementation in PyTorch are publicly available https / //t::/ /ggtttu...b.../ com/ jieyybii/i/i/ conssrrrit....t............
Implementation details. We generate instances at different hardness levels following prior works. For TSPTW [7, 9, 30, 67], we generate three types of instances: Easy, Medium and Hard, by adjusting the width and overlap of the time window. For TSPDL [68-70], we consider two levels of hardness: Medium and Hard. More details of such instance generation are provided in Appendix A. To ensure
7

---

Table Experiments on TSPDL instances with two different hardness.
50
100
Method
Infeasible
Infeasible %
Sol.
Inst. 4
Obj.
Gapl
Time
Sol.
Inst.
Obj-
Gap.
Time.
LKH3
0.00%
0.00%
10.87
0.00%
5.1h
0.00%
0.00%
16.39
0.00%
14h
ORTuols
100.00%
100.00%
/
10.9%
100.00%
100.00%
56.9.
Medium
Greedy-I.
100.00%
2.4m
100.00%
9.5m
Greedy-C
0.00%
0.00%
26.09
144,24%
9.1s
0.00%
0.00%
52.16
222.71%
27s
POMO*
17.72%
12.52%
10.98
3.80%
6.9%
49.39%
32.19%
17.11
9.15%
18s
POMO* PIP
2.21%
0.43%
11.22
3,41%
8.5s
2.88%
0.38%
17.71
8.08%
31s
POMO* PIP-D
2.64%
0.37%
11.26
3.78%
8.4s
2.14%
0.23%
17.84
8.86%
31s
LKH3
0.00%
0.00%
13.30
0.00%
6.8h
0.00%
0.00%
20.70
0.00%
1.2d
ORTools
100.00%
100.00%
10.64
100.00%
100.00%
56.84
Greedy-L
100.00%
100.00%
2.4m
100.00%
100.00%
9.4m
Greedy-C
0.00%
0.00%
26.07
99.73%
10.9s
0.00%
0.00%
52.17
156.37%
25s
POMO*
37.01%
29.25%
13.03
4.11%
6.8s
99.98%
99,88 99.85%
20.95
15.87%
18s
POMO* PIP
4.53%
2.10%
13.66
3.13%
8.5s
28.55%
20.66%
22.30
12.67%
318
POMO* PIP-D
3.89%
0.82%
13.80
3.95%
8.5s
12.84%
7.91%
22.84
12.32%
31s
comprchensive comparison, we also train and evaluate the models learned solely using our designed Lagrangian multiplier method. Meanwhile, we mark the models that use the Lagrangian multiplier with an for clarity. For our proposed approaches, our PIP models build on the Lagrangian multiplier by further incorporating one-step preventative infeasibility masking, while the enhanced version, PIP-D, is trained with a periodically and adaptively updated PIP decoder previously described. Hyper-parameters for training follow the original settings of the backbone models except for the ones related to the added PIP decoder. Detailed ppper-prraeetrrs and additional results are available in Appendix C and D. During inference, we adhere to the settings of the original backbone models. For the AM series models, greedy strategy with 8x augmentation; and for the GFACS series models, we employ 100 ants to generate solutions for each instance over 10 pheromone iterations.
sample 1280 solutions per instance; for the POMO series models, use
Baselines. We compare our proposed PIP framework with two types of baselines: 1) heuristic methods, including LKI13 [71], strong solver designed for multiple VRP variants; OR- [72], a more flexible solver allowing different combinations of multiple diverse constraints; and Greedy Heuristics that selects locally optimal candidates each step, where Greedy-L picks the nearest candidate and Greedy- C chooses based on complex constraints: in TSPTW, the soonest time window ends relative the current time; and in TSPDL, the minimal draft limit; 2) Neural methods, including the original AM [4], POMO [5] and GFACS [10], as well as JAMPR [73], adapted by [9] to solve TSPTW from VRPTW; and MUSIA [9], prior work on TSPTW trained in supervised manner, where OSLA is its one-step version and MUSLA adapt adopts an adaptive inference strategy. More details on the compared baselines are presented in Appendix C.
Evaluation metrics. In this paper, we report the following metrics to evaluate the performance of our proposed PIP framework: 1) the ratio of infeasible solutions (Infeasible% which includes the solution-level (Sol.) infeasible rate that considers all generated solutions during inference and the instance-level (Inst.) infeasible rate that considers the comprehensive results of N, solutions generated by the sampling (N, 1, 280 AM series models) or augmentation (N₂ = 8 in POMO series models). If at least one feasible solution is found among these N₂, solutions, the instance is considered to have feasible solutions; 2) average optimality gap (Gap) w.r.t the strong baseline LKH [71] for the best feasible solutions within N, solutions; 3) average tour length (Obj.) of the feasible best solutions within N, solutions; and 4) inference time, where we report the total time taken solve 10,000 (n 50 and 100) or 128 (n 500) instances, with batch parallelism enabled on a single GPU. For baselines run in CPU, we exhibit the results in parallel on 16 CPU cores.
5.1 Model performance on complex constrained problems
The performance comparison on TSPTW and TSPDL at various levels of problem hardness is presented Table 1 and Table 2, respectively. Notably, the original backbone models AM and POMO could not solve the problem even at the easiest level. By incorporating the Lagrangian multiplier (indicated by *), the models begin to generate some feasible solutions. However, this advantage diminishes under more complex constraints. For example, the instance-level infeasibility rates for
8

---

POMO and AM on Hard TSPTW- 100 reach 100% in Table I, which is dramatically reduced to 6.28% with the addition of PIP-D, while also improving solution quality. Compared to traditional heuristics like ORTools, Greedy-I, and Greedy-C, our PIP-D consistently outperforms these methods and shows favourable results against JAMPR and MUSLA, especially in large-scale problems. Furthermore, compared to PIP, our PIP-D) delivers competitive or even better objective values and optimality gaps while significantly enhancing training efficiency (e.g.. 1.5 times faster for n = 50 and 5.8 times faster for n 100, w.r.t POMO* + PIP). Notably, the superiority of PIP-D is more significant on the more constrained hardness levels and larger problem sizes. For TSPDL, we observe similar patterns, where our PIP and PIP-D models consistently outperform other baselines in terms of both infeasibility reduction and solution quality. These results validate that our PIP approach significantly reduces infeasible rates and substantially improves solution quality compared to existing neural methods.
5.2 Model performance on large-scale problems
We further evaluate the capability of solving large- scale problems by implementing our PIP framework
Table 3: Results on Medium TSPTW-500.
on GFACS [10]. As displayed in Table 3, equipping GFACS with our PIP significantly reduces the infea- sible rate, for both the solution level and instance level and simultaneously enhances solution quality. Notably, GFACS* * + PIP-D almost guarantees to ob- tain all feasible solutions. Different from AM and POMO, GFACS is NAR constructive solver, which showcases the generality of our framework.
Infeasible %
Method
Sol.
Inst.]
Gapl
Time!
LKHB
0.00%
0.00%
0.00%
26m
Greedy-L
100.00%
100.00%
3.2m
Greedy C
100.00%
100.00%
4.1s
GFACS*
58.20%
57.81%
21.32%
6.4m
GFACS* + PIP
4.72%
1.56%
13.04%
6.5m
GFACS* PIP-D
0.03%
0.00%
11.95%
6.5m
5.3 Further Experiments
Ablation on each PIP and PIP-D design. We now provide in-depth discussions on the effectiveness of the three proposed designs: the Lagrangian multiplier (*), the PI masking (PIP) and the learnable decoder (PIP-D). As shown in Tables 1 and 2, in Easy datasets, the solution-level infeasible rate for POMO* is 2.11%, improving to 0.06% with PIP-D. This shows that, for less complex constraints, the Lagrangian multiplier alone effectively guides the policy to feasible regions, hedging the impact of PIP and PIP-D, which aligns with Figure 2(b) and (d) where 11 is relatively large compared 11. However, in more complex scenarios, where 1e is much smaller relative to II (as in Figure 2(c)), the neural policy struggles even with the Lagrangian multiplier. In such cases, our PIP and PIP-D become crucial, significantly confining the search space as depicted in Figure 2(e). In Medium datasets, the infeasible rate drops from 18.7% in POMO* to 3.34% in POMO* + PIP-D; in Hard datasets, it drops dramatically from 100% in POMO* to 6.48% in POMO* + PIP-D. These results verify that our PIP framework achieves significant improvement, especially as problem complexity increases.
Ablation on the terms in Lagrangian function. In Figure 4, we exhibit the results with and without the JIN in E3), which validates its efficacy of enhancing the constraint awareness.
Jrw JN (Our)
5
Jin
Ablation on weighted balancing strategy. Recall that the ratio of infeasible to feasible samples in PIP labels varies with the inher- ent constraint hardness. Our preliminary experiments suggest that such a ratio can reach up to 20:1 in the case of Hard datasets, caus- ing significant label imbalance. This imbalance may significantly impact the performance of POMO* + PIP-D on several datasets, especially the harder ones, leading to 0% prediction accuracy on the minority class and causing a 100% infeasible rate for the backbone solver without a weighted balancing strategy. This indicates that the hardness-adapee
Sol.
Inst.
Gap
Figure 4: Effects of Jis
Eve- 200 (Ouno)
Eve- 100
2.5
0.0
Sol.
Inst.
Gap
Train T.
label balance strategy is essential. Moreover, for the accuracy of PIP-D. please refer to Appendix D.4.
Figure 5: Effects of Less Update.
Ablation on periodical update strategy. In Figure 5, we evaluate PIP-D models with fewer updates. Results show that more updates improve performance, despite a slight increase in training time.
Ablation on different step numbers. Instead of iterating over all future possibilities, we use one-step PI masking to approximate NP- harhard feasibility mask and reduce computational cost. To provide

---

Table 4: Results of PIP steps on Medium TSPTW-50.
Table 5: Results of PIP steps on Hard TSPTW-100
Method
PIP Step
Sol. Inbib
Enst. Inba
Gap!
Time]
Model
PLP Step
Sol. Infi
Inst. Inbi%)
Cap.
Time]
POMO*4RIP
76.90%8
47.28%
4.34%
19s
POMP>4PPP
100.00%
100,00%
POMO*#PIP
1
4.57%
0.90%
2.91%
15s
POMO*+PIP
1
31.49%
16.27%
0.57%
43s
POMO*ARIP
2
2,90%6
0.50%
2,9%%
4.2m
POMOS4PIP
2
36,875
12.88%
0.37%
15m
POMO++RIEDD
20,86'
3.49%
POMO-+PIIDD
79.73%
63.29%
0.31%
POMO-4P9RD
1
3,89%
0.69%
3,328
15s
POMO--PIND
1
13.189
6.48%
0.318
46
POMO*+FIPDD
2
2,59%
0.35%
3,34%
4.2m
POMO++PPPDD
11,62%
5.3%
0.31%
35m
Table 6: Results on LKH3 with the similar in- Table 7: Results LKH3 with the similar total stance inference time limit as POMOD+ inference time limit as POMO*+PIP(-D..
Methed
Itst. Time:
O1g-
Eeal. Infa5%
Ensd, Tise
Ohl
203
East Infa
Total Time
Imst. Indb
Total Time
Bast. Iofors
7.51
0.00%
-5%
10:31
D1075
LKRD (Duisat)
4.03
7.51
11001
8,30
10:21
0.000%
Laay
0133%
7.55
03.0%%
13.9%
30:12
Zio
1.51
19.29%
20s
101.00%
PONNO--PIP
0.338
7.50
03.0%%
13.94
30:57
DIRYS
21s
7.50
002002
45c
10:57
0.000%
01.38c
7.50
01.0%
11.04
30:66
21c
1.39
11.0%%
10.66
0.E05S
Medien
POMO
0.15%
POMO
0.59
LKHD (Dvfaakk
-0x
25.6L
0.12%
3.2m
$1.34
5076
LKHE (Daiala
76
25.51
0.22
1AU
$1.24
0.07%
LKHS
0.37a
25.43
30,9%%
0.59
43.04
90.38%
ERIT
226
108.005
51c
5031ers
PONOO-PIP PPIP
0.386
25.66
2.67%
0.5%
$1.42
16.37%
INIM
216
25.05
2.7%
48a
$1.42
16.775
POMOO-PIP.D I
0.386
25.69
3.00
0.5%
$1.50
5-486
216
25.09
3.0%
48a
$1.59
0.40%
comprehensive picture of the computational trade-off's, we further conduct experiments on PIP and PIP-D with different step numbers. In Table 4 and 5, we gather the results (solution feasibility and quality) and the inference time for different PIP steps. Results suggest that zero-step PIP saves time but suffers from unacceptable performance; the two-step PIP improves performance slightly but is computationally expensive. Hence, one-step PIP balances these trade-offs effectively.
Comparison with L.H3 under different inference time budget. To provide a more comprehensive comparison with LKH3, we provide additional results of LKH3 with identical time limits as the proposed approach across varying instance difficulty levels (Easy, Medium, Hard) and scales (n = 50, 100 nodes). The time limits are configured in two ways: matching the per instance inference time without parallelization and matching the total inference time with parallelization on a GPU, As shown in Table 6, POMO*+PIP(-D) outperforms LKH3 on Hard datasets, while maintaining competitive results on Easy and Medium datasets. While comparing per-instance time might seem fair for CPU-based LKH3, ignoring parallelization could disadvantage GPU-basee solvers (thus not fair for GPU-based solvers). To further explore this, we conduct another experiment but with a similar total inference time limit across both methods, which is common practice in most existing NCO papers. Results, in Table 7, show that our POMO* across most of the hardness. Moreover, leverage the strengths of both approaches and further reveal the practical usage of our method, we explore a hybrid method that combines our PIP(-D) framework with LKH3. The results, as shown in Appendix D.3, reveal that LKH3's search efficiency can be significantly enhanced when initialized with solutions from our PIP(-D) framework.
performs consistently better than LKH3
6 Conclusions
In this paper, we study an unsolved challenge in neural VRP solvers and correspondingly propose novel Proactive Infeasibility Prevention (PIP) framework to advance their capabilities towards addressing VRPs with complex constraints. Technically, we introduce Lagrangian multiplier method and preventative infeasibility masking to proactively guide the solution construction process. By further incorporating an auxiliary decoder, our PIP framework enhances training efficiency while exhibiting superior performance on more complex datasets. While our PIP generic and has shown great ability to boost both AR and NAR constructive methods, one potential limitation is that it may not improve performance on all backbone solvers and all VRP variants. Future directions include: 1) exploring other strategies to reduce computational complexity, such as employing trainable heatmap to confine the candidate space of PI masking calculation, 2) applying PIP to more neural methods at larger scales, 3) extending PIP to neural iterative solvers, 4) applying PIP to more VRP variants with complex constraints, including those hard-constrained VRPs whose feasibility masking is not NP-hard but with large optimality gaps, 5) exploring the applications of PIP in other domains, such as job shop scheduling, where operations need to be completed in specific order and infeasibility can be proactively prevented using PIP, and 6) developing theoretical justifications for PIP.
10

---

Acknowledgments and Disclosure of Funding
This research is supported in part by the National Research Foundation. Singapore under its AI and in part by the Singapore Ministry
Singapore Programme (AISG Award No: AISG3-RP-2022. of Education (MOE) Academic Research Fund (AcRF) Tier grant. We are grateful to Dr. Yingpeng Du and Dr. Yuan Jiang for the constructive discussions. We would like to thank the anonymous reviewers and AS) of NeurlPS 2024 for their constructive comments and service to the community.
References
[1] Grigorios Konstantakopoullss, Sotiris P Gayialis, and Evripidis Kechagias. Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification. Operational Research, pages 1-30, 2020.
[2] Lu Duan. Yang Zhan, Haoyuan Hu, Yu Gong, Jiangwen Wei, Xiaodong Zhang, and Yinghui Xu. Efficiently solving the practical vehicle routing problem: A novel joint learning approach. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 3054-3063, 2020.
[3] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d' d'horizon. European Journal of Operational Research, 290(2):405-22,, 2021.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn solve routing problems! In International Conference on Learning Representations. 2018
[5] Yeong-Dac Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pages 21 1188-21198, 2020.
[6] Cong Zhang, Yaoxin Wu, Yining Ma. Wen Song. Zhang Le, Zhiguang Cao, and Zhang, A review on learning to solve combinatorial optimisation problems in manufacturing. IET Collaborative Intelligent Manufacturing, 520)e 2023.
[7] Rongkai Zhang, Anatolii Prokhorchuk, and Justin Dauwels. Deep reinforcement learning for traveling salesman problem with time windows and rejections. In 2020 International Joint Conference on Neural Networks (JCNN), pages 1-8. IEEE, 2020.
[8] Qiaoyue Tang, Yangzhe Kong, Lemeng Pan, and Choonmeng Lee. Learning to solve soft-constrained vehicle routing problems with lagrangian relaxation. arXiv preprint arXiv:2207.09860, 2022.
[9] Jingxiao Chen, Ziqin Gong. Minghuan Liu, Jun Wang, Yong Yu, and Weinan Zhang. Looking ahead to avoid being late: Solving hard-constrained traveling salesman problem. arXiv preprint arXiv:2403.05316 2024.
[10] Minsu Kim, Sanghyeok Choi, Jiwoo Son, Hyeonah Kim, Jinkyoo Park, and Yoshua Bengio. Ant colony sampling with gflownets for combinatorial optimization. arXiv preprint arXiv:2403.077 2024.
[11] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, volume 28, pages 2692-27677 2700, 2015.
[12] Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In International Conference on Learning Representations Workshop Track, 2017.
[13] Mohammadreza Nazari, Afshin Oroojlooy, Martin Takáč, and Lawrence Snyder. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pages 1861-9871, 2018
[14] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 12042 12049, 2021.
[15] Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-NCO: Leveraging symmetricity for neural combinato- rial optimization. In Advances in Neural Information Processing Systems, 2022.
[16] André Hottung, Yeong- Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. In International Conference on Learning Representations, 2022.
11

---

[17] Jinho Choo, Yeong-Dae Kwon, Jihoon Kim, Jeongwoo Jae. André Hottung, Kevin Tiemnyy and Youngjune Gwon. Simulation-guided beam search for neural combinatorial optimization. In Advances in Neural Information Procexsing Systems, volume 35, pages 9760-8772, 2022.
[18] Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and lean-Mare Andreoli. BQ-NCO: Bisimulation quotienting for generalizable neural combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
[19] Felix Chalumeau. Shikha Surana, Clément Bonnet, Nathan Grinsztajn, Arnu Pretorius, Alexandre Laterre. and Thomas D Barrett. Combinatorial optimization with policy adaptation using latent space search. In Advances in Neural Information Processing Systems, 2023.
[20] Nathan Grinsztajn, Daniel Furelos- Blanco. Shikha Surana, Clément Bonnet, and Thomas D Barrett. Winner takes it all: Training performant RL populations for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
[21] Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Advances in Neural Information Processing Systems, 2023.
[22] André Hottung, Mridul Mahajan, and Kevin Tiemnyy PolyNet: Learning diverse solution strategies for neural combinatorial optimization. arXiv preprint urXiv:2402. 2404448,00.144888, 2024.
[23] Fu Luo, Xi Lin, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, and Qingfu Zhang. Self-improved learning for scalable neural combinatorial optimization. arXiv preprint arXiv:2403. 19561, 2024.
[24] Yeong-Dae Kwon, Jinho Choo, Iijoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. In Advances in Neural Information Processing Systems, volume 34, 2021.
[25] Jingwen Li, Yining Ma, Ruize Gao, Zhiguang Cao, Andrew Lim, Wen Song, and Jie Zhang. Deep rein- forcement learning for solving the heterogeneous capacitated vehicle routing problem. IEEE Transactions on Cybernetics, 2021.
[26] Federico Berto, Chuanbo Hua, Junyoung Park, Laurin Luttmann, Yining Ma, Fanchen Bu, Jiarui Wang. Haoran Ye, Minsu Kim, Sanghyeok Choi, Nayeli Gast Zepeda, André Hottung, Jianan Zhou, Jieyi Bi, Yu Hu, Fei Liu, Hyeonah Kim, Jiwoo Son, Haeyeon Kim, Davide Angioni, Wouter Kool, Zhiguang Cao, Jie Zhang. Kijung Shin, Cathy Wu, Sungsoo Ahn, Guojie Song, Changhyun Kwon, Lin Xie, and Jinkyoo Park. RL4CO: an extensive reinforcement learning for combinatorial optimization benchmark. arXiv preprint 2336v 17100, 2023.
(27] Jianan Zhou, Zhiguang Cao, Yaoxin Wo, Wen Song, Yining Ma, Jie Zhang, and Xu Chi. MVMoB: Multi- task vehicle routing solver with mixture-of-experas In International Conference on Machine Learning. 2024.
[28] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv: 190::00060.222. 2019.
[29] Zhang-Huu Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7474-7482, 2021.
[30] Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic programming for vehicle routing problems. In International Conference on Integration of Constraint Programmingg Artificial Intelligence, and Operations Research, pages 190-213. Springer, 2022.
[31] Ruizhong Qiu. Zhiqing Sun, and Yiming Yang. Dimes: A differenniable meta solver for combinatorial optimization problems. Advances in Neural Information Processing Systems, 35:25531- -255466, 2022.
[32] Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. Advances in Neural Information Processing Systems, 2023.
[33] Yimeng Min, Yiwei Bai, and Carla P Gomes. Unsupervised learning for solving the travelling salesman problem. Advances in Neural Information Processing Systems, 2023.
[34] Haoran Ye, Jiarui Wang, Zhiguang Cao, Helan Liang, and Yong Li. DeepACO: Neural- ant systems for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
[35] Yifan Xia, Xianliang Yang. Zichuan Liu, Zhihao Liu, Lei Song, and Jiang Bian. Position: Rethinking post- hoc search- based neural approaches for solving large-scale traveling salesman problems. In International Conference on Machine Learning, 2024.
12

---

[36] Xinyun Chen and Yuandong Tian. Learning perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 32, pages 6281-6292, 2019.
[37] Hao Lu, Xingwen Zhang. and Shuang Yang. A learning-based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2020.
[38] André Hottung and Kevin Tierney. Neural large neighhorhood search for the capacitated vehicle routing problem. In European Conference on Artificial Intelligence, pages 443-450. IOS Press, 2020.
[39] Paulo da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Eren Akçay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning, pages 465-480, 2020.
[40] Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems, 335)):50777506,, 2021.
[41] Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song. Le Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In Advances in Neural Information Processing Systems, volume 34, pages 11096-11 1107, 2021.
[42] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Neurolkh: Combining deep learning model with lin- seeriighnn-helsgau heuristic for solving the traveling salesman problem. In Advances in Neural Information Processing Systems, volume 34, pages 7472-7483, 2021.
[43] Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. cal search for the traveling salesperson problem. In International Conference Learning Representations, 2022.
Graph neural network guided lo-
[44] Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Hongliang Guo, Yuejiao Gong, and Yeow Meng Chee. Efficient neural neighborhood search for pickup and delivery problems. In Proceedings of the Thirty-Fira International Joint Conference on Artificial Intelligence, pages 4776-4784 2022.
[45] Yining Ma, Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt. In shirty-seventh Conference Neural Information Processing Systems, 2023.
[46] Sirui Li, Zhongxia Yan, and Cathy Wu. Learning delegate for large-scale vehicle routing. Advances Neural Information Processing Systems, 34:26198-266 26211, 2021.
[47] Zefang Zong. Hansen Wang. Jingwei Wang, Meng Zheng, and Yong Li. Rbg: Hierarchically solving large-scale routing problems in logistic systems via reinforcement learning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4648-4658, 2022.
[48] Hanni Cheng. Haosi Zheng, Ya Cong, Weihao Jiang, and Shiliang Pu. Select and optimize: Learning aolve large-scale tsp instances. International Conference on Artificial Intelligence and Statistics, pages 1219-1231. PMLR, 2023.
[49] Yan Jin, Yuandong Ding. Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, and Jiang Bian. Pointerformer: Deep reinforced multi-pon pointer transformer for the traveling salesman problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 81.2-81400 8140, 2023.
[50] Xuanhao Pan, Yan Jin. Yuandong Ding. Mingxiao Feng. Li Zhao, Lei Song, and Jiang Bian. H-tsp: Hicrarchically solving the large-seale traveling salesman problem. Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages
2023.
[51] Qingchun Hou, Jingwei Yang, Yiqiang Su, Xiaoqing Wang. and Yuming Deng. Generalize learned heuristics to solve large-scale vehicle routing problems in real-time. In International Conference on Learning Representations, 2023.
[52] Haoran Ye, Jiarui Wang. Helan Liang, Zhiguang Cao, Yong Li, and Fanzhang Li. Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024.
[53] Chaitanya K Joshi, Quentin Cappart, Louis Louis-Martin Rousseau, and Thomas Laurent. Learning tsp re- quires rethinking generalization. In International Conference on Principles and Practice of Constraint Programming, 2021.
13

---

[54] Zeyang Zhang. Ziwei Zhang, Xin Wang, and Wenwu Zhu. Learning to solve travelling salesman problem with hardness-adaptive curriculum. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
[55] Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Iearniig generalizable models for vehicle routing problems via knowledge distillation. In Advances in Neural Information Processing Systems, 2022.
[56] Jiwoo Son, Minsu Kim, Hyeonah Kim, and Jinkyoo Park. Meta-SAGE Scale meta- -eatnne scheduled adaptation with guided exploration for mitigating scale shift combinatorial optimization. In International Conference on Machine Learning. 2023.
[57] Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards auni-generalizable neural methods for vehicle routing problems. In International Conference on Machine Learning, pages 42769- 42789. PMLR, 2023.
[58] Chenguang Wang, Zhouliang Yu, Stephen McAleer, Tianshu Yu, and Yaodong Yang. ASP: Learn universal neural solver! IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
[59] Simon Geisler. Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski. and Stephan Günnemann. Generalization of neural combinatorial solvers through the lens of adversarial robustness. In International Conference on Learning Representations, 2022.
[60] Han Lu, Zenan Li, Runzhong Wang. Qibing Ren, Xijun Li, Mingxuan Yuan, Jia Zeng, Xiaokang Yang. and Junchi Yan. ROCO: A general framework for evaluating robustness of combinatorial optimization solvers on graphs. In International Conference on Learning Representations. 2023.
[61] Chengrun Yang, Xuezhi Wang. Yifeng Lu, Hanxiao Liu, Quoc V Le. Denny Zhou, and Xinyun Chen. Large language models as optimizers. In International Conference on Learning Representations, 2024.
[62] Shengeai Liu, Caishun Chen, Xinghua Qu, Ke Tang, and Yew-Soon Ong, Large language models as evolutionary optimizers. arXiv preprint arXiv:2310.1 19046, 2023.
[63] Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Evolution of heuristies: Towards efficient automatic algorithm design using large language model. In International Conference on Machine Learning, 2024.
[64] Hang Zhao, Qijin She, Chenyang Zhu, Yin Yang, and Kai Xu. Online 3d bin packing with constrained deep reinforcement learning. In Proceedings the AAAI Conference on Artificial Intelligence, volume 35, pages 741-749, 2021.
[65] Ronald J Williams. Simple statistical gralient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3):229 256, 1992.
[66] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large TSP instances. In Proceedings of the AAAI Conference Artificial Intelligence, 2021.
[67] Rodrigo Ferreira Da Silva and Sebastián Urrutia. A general vns heuristic for the traveling salesman problem with time windows. Discrete Optimization, 7(4):203-2) 211, 2010.
[68] Jørgen Glomvik Rakke, Marielle Christiansen, Kjetil Fagerholt, and Gilbert Laporte. The traveling salesman problem with draft limits. Computers & Operations Research, 390):2161-2167, 2012.
[69] Raca Todosijević, Anis Mjirda, Marko Mladenović, Said Hanafi, and Bernadd Gendron. general variable neighborhood scarch variants for the travelling salesman problem with draft limits. Oprimization Letters, 11:1047-1056, 2017.
[70] Shahin Gelareh, Bemaar Gendron. Said Hanafi, Rahimeh Neamatian Monemi, and Raca Todosijević. The selective traveling salesman problem with draft limits. Journal of Heuristics, 26:339-352, 2020.
[71] Keld Helsgaun. LKH-3 (version 3.0.7), 2017. URL http::/ http://uru..kk/eellleeeeerraa LKH-3/.
[72] Vincent Furnon and Laurent Perron. Or-tools routing library. URLLattpp://derelpprr....go com/ aptimization httiiioo//rotng///////
[73] Jonas K Falkner and Lars Schmidt- Learning to solve vehicle routing problems with time windows through joint attention. arXiv preprint arXiv:2006.09100. 2020.
[74] Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, and Iddo Drori. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint arXiv: 1911.0493, 2019.
14

---

[75] Majed G Alharbi, Ahmed Stohy, Mohammed Elhenawy, Mahmoud Masoud. and Hamiden Abd El- Wahed Khalifa. Solving traveling salesman problem with time windows using hybrid pointer networks with time features. Sustainability, 13(22):12906, 2021.
[76] Quentin Cappart, Thierry Moisan, Moris-Martin Rousseau, Isabeau Cire. Combining reinforcement learning and constraint programming for combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
and Andre A
[77] Yvan Dumas, Jacques Desrosiers, Eric Gelinas, and Marius Solomon, An optimal algorithm for the traveling salesman problem with time windows. Operations research, 43(2):367-371 1995.
15

---

Learning to Handle Complex Constraints for Vehicle Routing Problems (Appendix)
A Details of considered VRPs
In this paper, we mainly consider two VRP variants with complex interdependent constraints: Traveling Salesman Problem with Time Window (TSPTW) and TSP with Draft Limit (TSPDL). We first detail their corresponding data generation process, then demonstrate the interdependent nature of constraints inherent in these problem variants.
A.1 Traveling salesman problem with time window (TSPTW)
Each TSPTW instance includes depot node and customer nodes with four properties: 2- dimensional coordinates Euclidean space (Ie y1), lower bound (4) and upper bound (u;) of time windows. In prior works [7, 9, 30, 67], they generate the coordinates following uniform distribution confined in a square box (æ,, 34) ~ [4 100] while generating time window differently. Concretely, there are three ways to synthesize the time window: 1) construct near-optimal TSP solution first and generate the time window according to the distance between the two adjacent nodes in the pre-generated near-optimal solution (e.g. in [74, 75]); construct random node permutation first and generate time window according to the distance between the two adjacent nodes in the pre-generated random solution (e.g. in [30, 67, 76]); and 3) generate the time window under uniform distribution without prior TSP permutation (e.g. in [7, 9I). The first two methods generate the time window based a pre-generated TSP solution which can guarantee the existence of feasible solutions for the generated instances. However, they diminish the impact of time window constraints due the strong prior knowledge of TSP and the pre-generated solutions. Mcanwhile, the first method necessitates obtaining a near-optimal solution for TSP initially, which incurs additional computational costs. In contrast the first two methods, the third method appears more generic but does not guarantee feasibility. Below, we describe the detailed settings for instance generation, considering three different levels of hardness, as outlined in the main paper.
Easy TSPTW. We mainly follow the settings from recent works [7, 9] and employ the third method presented above generate time window. In specific, the lower bound of the time window I, follows uniform distribution, i.e., 4 ~ 10,0 Tw.. where T' is an estimator of expected tour length in relation to the problem scale. For example, T20 10.9 [9]. The upper bound of the time window u, is generated based on 4, where u, 4, + TN U[[a, 3], and a and / are set to 0,5 and 0.75, respectively.
Medium TSPTW. It follows the same settings of the easy TSPTW, except that and / are set to 0.1 and 0.2, respectively. To decrease a and B3, we derive TSPTW instances with tighter time windows, resulting in increased hardness level.
Hard TSPTW. Different from easy and medium TSPTW, hard instances are generated following the settings of the benchmark dataset [67]. The second method is leveraged to generate time window. Concretely, we first obtain a permutation T by randomly shuffling nodes. Then, the time window generated based on r following a uniform distribution, 4 ~ U [t>: 7). vhi and uą ~ U [th,, v/s + 17). where v denotes the cumulative distance of the partial solution until time step i. 17 is a factor to control the width of the time window. As preliminary experiments [9] suggest, the original at 500, allowing the instance to achieve optimality using a simple greedy heuristic. Hence, this paper, we 7) to 50 to generate tighter time windows and increase hardness.
set
Following the conventions [4. 5], we normalize the node coordinates into [o, 1] by dividing scale factor p 100. Pertaining to the time window, we also divide 4 and u; by In specific, following [30], we first modify the upper bound of the depot un to the maximum value of the upper bound of time window among all the customer nodes plus the travelling distance between them, i.e, max(u, (u; + I|u - roll2). E [1, n).. Then we use up as the normalization factor, scaling all 1 and u; by it to confine their values within the range of [0, 1].
16

---

A.2 Traveling salesman problem with draft limit (TSPDL)
TSPDL prevalent in marine transportation scenarios, which consider the vessel capacity of the freighters. Each node has its own demand 6; and draft limit d, A TSPDL instance is derived from TSP instance by mutating the draft limit to less than the total demand for a% of nodes, i.e., d, (6, = while the draft limits of remaining nodes are equal to the total demand, i... d; = مー= 6.. We can adjust a to manipulate the hardness of the TSPDL dataset. The demand is set to for customer nodes or zero for depot node to following benchmark datasets [68, 69, 71J. The mutation proportion 5% varies, being either random value or fixed to 10, 25, 50, or 75 percent. We observe that small 5% results in a simple TSPDL dataset that can be effectively managed with heuristics. In this paper, we focus on relatively hard problems by setting a% to 75% for the Medium dataset and 90% for the Hard dataset. Note that the availability of feasible solutions can be guaranteed through the feasibility check, as demonstrated in the following Py PyTorch implementation.
node_ dode_demand torch. cat ([torch. (ettocc.zeroodd zeros ((batch_ssie sizee, 1)), torch. ones (batch_size, problem_size smize 1))], dim-1) # shape: (batch_size problem_sizo lemand_sum = node_demand. sum (dimm11)) unaqueeze (1) for i in range (batch_size):
feasible False
while not feasible:
# mutation of dl randomly occurs in w% of the nodes except the depot mutation = forch.randint((. demand_sum[i] [u]mmm]]aaaaa int () i),m(), size = (problem_size sigma // 100.))
count torch.bincour (mutation)
count_ cumsum torch. cumsum (count, dim-O)
feasible = (count_ cumsum <= torch arange count.size (0))).).a1)))))
To summarize, the feasibility guarantee based on the data generation rules described above, and its corresponding accessibility by K.HH3 [71] presented in Table 8. For example, the data generation process of the easy TSPTW dataset cannot theoretically guarantee the existence of a feasible solution for each test instance. However, LKH3 find (at least) one feasible solution for each test instance. These results showcase that feasible solutions consistently exist for the synthetic test instances (or datasets) used in this paper, with any reported infeasibility arising solely from the method itself.
Table 8: Feasibility guarantee based on the generation rules and the accessibility by LKH3.
Variant
Hardness
Feasibility Guarantee
Feasibility Accessibility by LKH3
Easy
TSPTW
Medium
Hard
Medium
TSPDL
Hard
A.3 Irreversible solution infeasibility
As mentioned in Section 4, exiting masking mechanism fails to handle problems with complex interdependent constraints (e.g., TSPTW and TSPDL), since may cause irreversible solution infea- sibility during solution construction. Here, we provide a detailed explanation of how our preventative infeasibility masking helps twist the irreversible solution infeasibility, as illustrated in Figure 6. Given a 5-node (Vo, U1, U2, U3, U4) TSPTW instance with the time window {[0. 7], [1, 4], [5, 7], [2, 5), [4, 7]}. and the current partial solution Vp + U1. we derive the preventative infeasibility mask by assuming that one of the candidates (U2, V3, v2a) is visited and check the accessibility of assumed arrival time for remaining unvisited nodes. As shown in the left panel, we assume that U/2 is the next visited node and see what would happen if we travel from Uo + 01 + to remaining unvisited nodes Ut and u4. We notice a constraint violation on the assumed tour Up + U1 -> 122 -> 0g since the assumed current time is already 5 at node t2; thus, the earliest arrival time to U3 is 7, which falls outside the time window of 0z. Note that another assumed tour vo - 01 -> 12 -> va will also violate the time window of 03 in the end, since it further pushes the assumed arrival time at U3. Therefore, 82
17

---

Travelling Time
Time Window:
Artival Time (Feaeble)
Artival Time (Ilicaaitle)
Lnvished Node
Valted Nodk
Assumed Visted Node
Potecnal Indeasible Node
Vistel Rdge
Assumed Visital Fége
-*p Inscesitle Edge
-*p Accesible Edge
1-00
eB L
2 1
0
Preventative Infeasible Nodes
Feasible Nodes
Figure 6: A TSPTW example of Preventative Infeasibility Masking in handling irreversible solution infeasibility. dark green square denotes an unit of the travel time. No service time considered.
is marked as an infeasible node by our preventative infeasibility masking, and then it will further consider other candidate nodes (i.e., V/ and 24). given the current partial solution Uh - 01, following the same logic. Intuitively, this infeasibility is caused by the wrong selection of 22 in the current step, which pushes the current time to a high value that exceeds time windows of some remaining unvisited nodes, resulting in irreversible solution infeasibility. With that said, once some candidates with late time windows have been selected, will cause a lapse of current time, which irreversibly influences the remaining unvisited nodes (c.g.. with early time windows) in future steps of solution construction. Such phenomena can also be observed in other interdependent constraints that exhibit incremental or quantified properties, such demand-related constraints, vehicle number constraints, etc.
B Network architecture of PIP decoder
The network architecture of our PIP-D framework generally mirrors that of the backbone model, but it incorporates dual decoders (i.e.. routing decoder and PIP decoder). For the PIP decoder, replace the final output layer with a Sigmoid layer to adjust the output range, unless the backbone model's last layer is already a Sigmoid, in GFACS [10], in which case replacement necessary.
Specifically, the AR backbone models AM [4] and POMO [5] share similar architecture, with multi-head attention (MHA) layer serving as the foundation. Without loss of generality, we take POMO decoder as an example for a demonstration purpose. As shown Figure 3, the decoder receives the node embedding h;, the solution embedding ht,, and the real-time solution feature I as inputs, which are then used to compute the query (q), key (k), and value (v) for the MHA layer:
gº = Wiehe, J*)
=
-W.hh
(5)
where W q. W.e and hhth parameter matrices of the be (b E [1, B) attention head, and [.] denotes the concatenation operator. The output of the MHA layer is calculated as:
(Q
a' = Σ Softmax
(6)
Vdd
1
where de is the dimension of the key. Subsequently, the output of each head passes through linear layer parameterized by W., resulting in h2 W [a", at at...., .........) 3) The decoder then computes selection probabilities for all candidates nodes using single-head attention layer:
1hThi (Vdn
p; = Softmax (5-tanh,
where d, is the dimension of the node embedding. & is used to clip the logits to encourage policy exploration [4, 5]. For binary classification tasks in the PIP decoder, we replace the final output layer (i.c., the Softmax layer in the above equation) with Sigmoid layer.
18

---

In contrast to AM and POMO, the encoder of GFACS outputs edge embeddings, and the decoder consists of 3-layer multilayer perception (MLP). Each edge embedding h. is processed through:
h/= ((W))))
(8)
where 1 E [0. denotes the layer index, W₁ represents a linear layer. and ((-) is an activation function, i.e. SiLU for / 0, and Sigmoid for / = Given the significant correlation between preventative infeasibility masking and the current partial solution Tı, we convert its NAR decoder an AR one by adding an extra input layer that integrates the embedding of the last edge he, in To and the current solution feature f into the edge embedding itself, i.e., he = [ihe he., f Note that GFACS only consider? R (nearest) edges for each node. But for complex constrained problems (e.g.. TSPTW), travelling distance may not be sufficient. Instead of using distance as the sole criterion, we select the ğ neighbors for each node based on the extent of time window overlap, defined as (min(u; uz) max(|s; 12)) for all customer nodes. For the depot, since time window overlap is less relevant, we select z nodes with the earliest
5
C Experiment details
We mark the model with Lagrangian multiplier objective function as (e.g., AM*), and the model further with the preventative infeasibility masking as PIP (e.g.. AM*+PIP), We follow their original setups (e.g., model architectures and hyper-parameters) in AM [4], POMO [5] and GFACS [10]. Pertaining to the PIP-D model (e.g.. AM*+PIP-DD we employ an auxiliary decoder (i.e., PIP decoder) that is trained with the ground-trume --tutthh PIP labels in a supervised manner. To balance the trade-off between training efficiency and empirical performance, we update it periodically. Specifically, within E total training epochs, the PIP decoder is first trained with Emit epochs, and then periodically updated E. epochs per E, epochs. To boost the performance, we switch E,, to Eg for the final E epochs. The detailed settings are presented in Table 9. For the training epochs that utilize the outputs of the offline (i.e., freezed) PIP decoder the preventative infeasibility masks, we employ the best-so-far PIP decoder that achieves the highest accuracy on feasible samples, since inaccurate predictions can lead to the exclusion of some feasible candidates. We set the Lagrangian multiplier to in the main experiments, with further analyses presented in Appendix D.I.
Table 9: Hyper-parametee of the periodical update strategy for PIP decoder.
Method
n
E
Emit
Ep
En.
E
50
10000
200
1000
50
50
POMO* PIP-D
100
10000
100
1000
20
50
AM PIP-D
50, 100
100
10
10
5
GFACS* PIP-D
500
50
10
Baselines. We compare our proposed PIP framework against the following baselines, with implemen- tation details provided below:
LKH3 [71], a strong solver designed for a wide range of VRP variants, which we use to generate the (near-)optimal solutions for the test instances with 10,000 trails and I run.
OR-Tools [72], more flexible solver allowing different combinations of diverse constraints, which we employ the local cheapest insertion as the first solution strategy and the guided local search as the local search strategy with time limit μ for each instance (i.e., 20s for n = 50 and 40s for n = 100 following [27]). As for TSPDL, we have tried all first solution strategies outlined in the official documentation, yet we still fail find any feasible solution.
Greedy Heuristics, a classical hand-crafted method considering the local optimal candidates at each step. The Creedy-L heuristic selects the candidate with the shortest distance, and the Greedy-C heuristic selects node based on the satisfaction of constraints, which the candidate with the soonest time window end w.r.t current time in TSPTW and the candidate with the minimal draft limit in TSPDL.
AM [4), milestone neural AR constructive solver leveraging the Transformer architecture. We implement TSPTW and TSPDL following its default settings.
19

---

POMO [5]. enhanced constructive solver upon AM by considering the symmetry property of VRP solutions. POMO shares similar architecture with AM. We implement TSPTW and TSPDL following its default settings except removing its stipulated starting node due to the unsuitability to the complex constrained problems, which also noted in [22].
GFACS [10], neural NAR constructive solver, which introduces the generative flow net- works (GFlowNets) to improve the canonical ant colony optimization (ACO) algorithm. incorporates heuristic matrix and a pheromone matrix, where the former parameterized with a neural network, and the latter is updated based on the exploration of multiple ants. We implement TSPTW on it following its default settings.
JAMPR [73], state-of-the-art model for similar problem variant VRPTW, which was further adapted by [9] to solve TSPTW. In this paper. we directly report its result listed in [9] due to the unavailability of source code.
MUSLA [9], a recent method with designs tailored for TSPTW, incorporating problem- specific features and large supervised learning dataset, where OSLA is its one-step version and MUSLA adapt adopts an adaptive inference strategy to balance the optimality gap and the solution feasibility. Results are adopted from [9] due to the unavailability of source code, with our 'Eay'' setting corresponding to their 'Medium' one in [9].
D Additional analyses and discussions
D.1 Effects of different Lagrangian multiplier X
Our PIP leverages the Lagrangian multiplier method to guide neural policy search. While some existing methods, such as [8], employ bi-level optimization techniques to jointly up- date the Lagrangian multiplier and the primal objective function, we find these approaches to be inefficient. Therefore, we opt to fix the value of the Lagrangian multiplier À and fo- cus solely on optimizing the primal variables in this paper. Here, investigate the effect of different Lagrangian multipliers on the so- lution quality and feasibility. The results shown in the left panel of Figure 7, where we observe that larger results in lower in- feasible rate but with an increased optimality gap. whereas smaller reduces the optimal- ity gap but at the expense of a much higher infeasible rate. Consequently, we set for a balance, prioritizing the optimization of the primal objective function.
A-03
Figure 7: Radar chart of the model performance with different Lagrangian multipliers X, including the met- ries of the solution-level infeasible rate (Sol.), the instance-level infeasible rate (Inst.) and the optimal- ity gap (Gap).
D.2 Performance comparison on overlap feasible instances
We report the average objective values and optimality gaps in Tables I and 2. It should be noted, however, that these metries are calculated across different sets of feasible instances. Considering that a complete overlap of feasible instances across all baselines is impractical (due to the 100% infeasibile rates of some baselines), we present additional results on set of overlapped feasible instances across POMO variants to facilitate more conprehensive comparison. As shown in Table 10, the models with our PIP consistently outperforms POMO in terms of solution quality. On the easy dataset, PIP-D exceeds PIP due to the incorporation of data augmentation during inference. In summary, despite the different instance sets, the optimality gaps displayed in Table (wo overlap) exhibit numerical patterns and conclusions that align with those empirically observed on the overlapped sets.
20

---

Table 10: The optimality gap of overlapped feasible instances among 10000 TSPTW-50 instances.
Method
Gap
Overlap Gup w: Aug.
Overlap Gap Aug.
POMO*
3.08%
3.08%
5.95%
Easy
POMO PIP
2.65%
2.65%
4.87%
POMO PIP-D
2.51 %
2.51
6.51%
Overlap number
10000
Mediam
POMO
5.23%.
5.22%
6.83%
POMO PIP
2.91 %
2.89%
4.43%
POMO PIP-D
3.32%
3.28%
4.84%
Overlap number
9524
8067
POMO
1.61%
1.66%%
Hard
POMO PIP 0.18%
0.18%
0.26 %
POMO PIP-D
0.28%
0,28%
0.42%
Overlap number
6336
5758
D.3 Discussion on reducing the computational complexity
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 computationally inefficient. Therefore, we approximate it with one-step PI masking, whose efficiency is validated in Table 4 and Table 5. 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. Besides, we further explore some strategies for accelerating the training and inference of PIP.
Apply sparse strategies to refine PIP calculations. Due to the O(n²) complexity of PIP, applying to all the unvisited candidate nodes will be computationally expensive. For large-scale problems, we only consider top K neighbours, which is implemented on GFACS. Results in Table 3 show that GFACS*+PIP-D maintains similar training and inference times GFACS# TSPTW-500 (i.e., 28.3h and 6.5m vs. 28. Ih and 6.4m).
Couple with the state-of-the-art solvers (e.g. LKH3). Our PIP is empirically verified to be efficient due its capability to obtain good and feasible solutions within very short time (LKH3: 1.4d vs POMO*+PIP-D 48s), while LKH3 can get near optriml solutions with prolonged time. leverage the strengths of both approaches, we use our PIP-D to provide better initial solutions for IKH3. As shown in Table 11, this combination reduces the infeasibility rate from 53.1 1 % to 0.21% % and improves the objective from 51.65 to 51.25 22.25 within only few seconds per instance. 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). We also show the progress objective value and instance-level infeasibility rate over inference times in Figures 8, for clearer comparison.
Fine-tune I Lagrangian method (*) with PI masking. On top of the basic Lagrangian method (e.g., POMO*), PIP further employs the preventative infeasibility (PI) masking throughout the training process. We would like to note that there is another way to exploit the preventative infeasibility information and reduce the computational complexity, i.e., by leveraging the PI mask fine-tune the pretrained Lagrangian method. The comprehensive empirical results on Medium TSPTW-50 are shown in Table 12, where the first two methods denote the PIP and Lagrangian methods applied to POMO, respectively. The results indicate that a few steps of fine-tuning the Lagrangian method using PIP masks can yield favorable improvements in the feasible rate and the optimality gap, and significantly reduce the training complexity as well.
Early stop of PI masking. At each solution construction (i.e., decoding) step, our PIP leverages preventative infeasibility masking to proactively steer the policy search to (near- feeasible regions, leading to increased computational overheads as the problem sizes scale up. Here, we explore the potential of early stopping PIP, where PIP is only employed during the initial steps of solution construction. Based on our empirical observation depicted the left panel of Figure 10, infcasibility predominately occurs in the first few steps of the entire
21

---

process. This observation reveals the possibility of merely acquiring PI masks for the initial few steps, which could improve the training efficiency. We leave future work.
Table 11: Results of LKH3 and POMO*+PIPAM under different time limits.
Method
Tnit. Sol.
LKH3 Max Trials
Total Time
Inst. Time
Inst. Infsh %
Obj.
LKH3
Default
10000
14d
3.2m
0.07%
51.24
LKH3
Default
5000
22.5h
2.2m
0.19%
51.24
LKH3
Default
1000
4h
2.57%
51.26
LKII3
Default
100
53m
5.1s
53.11%
51.65
POMO*+PIP-D POMO*-PIP-D+LKIT DHL
48s
6.48%
51.39
POMO*+PIP-D POMO*+PIPDD
100
53m
5.1s
0.21%
51.25
POMO*<PIP-D+LKE
1000
9h
52s
0.05%
51.24
50
LKH3
LKH3
PIMOD++PP-DD+LRRE POMO*+PIP-D
51.6
POMO* POMMD*+PIPDD+LKR LKHH
POMO*+PIPM PIP-D
40
Inst Infobrt
51.5
51.38
Obi.
8
20
51.4
$1.36
2.0
1.5
10
Time
51.3
0
50
100
150
200
50
100
200
Time (5)
Time (5)
Figure 8: Average infeasibility rates over time.
Figure Average objective values over time.
Table 12: Experimental results of different fine-tuning settings on Medium TSPTW-50.
Infeasible Sol.)
Training epoch with Fine-tune epochs with
Training Time
Inst.]
Obj-
Gapl
10000 (POMO* + PIP)
120h
4.53%
0.90%
13.38
2.91%
10000 (POMO*)
0
60h
14.92%
3.77%
13.68
5.23%
10000
100
61.3h
4.45%
1.03%
13.61
4,56%
9900
100
60.7h
5.20%
1.31%
13.60
4.45%
9000
1000
5.63%
1.24%
13.55
4.08%
10'
Accuncc
Accursy
Povenage (16)
10'
06
Specificity
Recall
Beaal
10'
52
Surring
Easy
Mediu
Figure 10: Right panel: Log-scale barplot of frequency stats of the starting infeasible node index.
Middle panel: Evaluation metrics on TSPTW-50. Right panel: Evaluation metrics TSPDL-50.
D.4 Analyses of PIP decoder accuracy
We use an auxiliary decoder (i.e., PIP decoder) in the proposed PIP-D framework, whose goal is to learn and predict Pl masks by identifying infeasible candidates based on the current partial solution. We formulate binary classification task. Here, we demonstrate the efficacy the learned PIP decoder through various evaluation metrics, including accuracy, recall (of infeasible samples), and
22

---

specificity (recall of feasible samples). As shown in the last two panels of Figure 10, our PIP decoder can accurately predict the masks across all hardness levels in TSPTW and TSPDL, especially for the more complex constrained one. This indicates that our PIP decoder aligns well with the goal of ensuring high accuracy in feasibility predictions.
D.5 Performance under different inference time budget.
For a fair comparison, we also extend the inference time (by sampling more solutions and data augmentation) of the baselines to similar as POMO PIP and POMO + PIP-D, Results show that incorporating the Lagrangian multiplier (POMO* and AM*) may lead to some improvement (in Table and 2). but not for the cases in Table 13 under complex constraints and larger scales. Even with prolonged inference time, existing methods do not deliver any feasible solutions for the studied complex constrained VRP. contrast, our PIP-D with 48s time significantly reduces infcasibility from 100% to 6.48% compared to baselines running for 2.5m, and exhibits an optimality gap of around only 0.3%. Furthermore, PIP can perform even better with more inference time.
Table 13: Results under different times on Hard TSPTW-100.
Method
Inst. Infsb %
Gap
N,
Time
POMO (short)
100.00%
8
21s
POMO (long)
100.00%
/
80
2.5m
POMO (short)
100.00%
8
21s
POMO* (long)
100.00%
80
2.5m
POMO*+PIP (short)
16.27%
0.37%
8
48s
POMO*+PIP (long)
11.75%
0.33%
24
2.4m
POMO*+PIP-D (short) POMO*+PIP-D (long)
6.48%
0.31%
48s
5.19%
0.28 %
24
2.4m
D.6 Sensitivity analyses
Statistical significance. To validate the statistical significance of experiments, we first conduct the Kolmogoroy-Smirrot test to identify the normality of the evaluation metrics. The results indicate that the optimality gap, solution-level infeasible rate, and instance-level infeasible rate are not normally distributed. Hence, we employ the Wilcoxon test to evaluate the statistical significance. As revealed in Figure 11, the performance disparity among different methods significant across all hardness levels. especially in more complex constrained problems, underscoring the effectiveness of our method. Note that this result further supports the improvement of our PIP framework reported in Table 1.
12.5
#
10.0
15
# t
7.5
10
3.0
2
255
0
-25
P0M0
POMO PIP POMO : MIND
POMO*
POMO PIP POMO* PIP-D
POMO
POMO + PIP POMO + PIP-D
Easy TSPTW
(b) Medium TSPTW
Hard TSPTW
Figure 11: Boxplot of the optimality gap. In the boxplot, the ssymol denotes statistical significance, where *** ** and * indicate significant differences between models with p-values 0.001, 0.01, and 0.05, respectively, based on the Wilcoxon test.
Performance under different hyper-parameters. We explore the variance in model performance under different hyper-parameter parameters. We fix the total update epoch of the PIP decoder and adjust its interval. Results in Table 14 demonstrate that our PIP model robust to different interval settings within the same total update epoch. However, reducing the number of updates, shown in Figure 5,
23

---

leads to decline in model performance. Additionally, we present results using different normalization layers. Although further adjustments the model architecture can enhance performance (e.g.. using layer normalization), we adhere to the conventional settings outlined in [4] for fair comparison.
Table 14: Sensitivity analyses of hypereparamettess on Medium TSPTW-50.
Infeasible% Sol.
Infeasible %
Emit
Ep
E,
E
Inst.
Gap
Normalization
Sol.
Inst.
Gap
200
1000
50
50
3.83%
0.65%
3.32%
Instance (Ours)
3.83%
0.65%
3.32%
200
500
25
25
3,41 %
0.68%
3.36%
Batch
4.14%
0.96%
3.10%
200
100
5
5
4.60%
1.00%
3.34%
Layer
4.15%
0.58 %
2.75%
D.7
Benchmark performance
We further evaluate PIP framework on the benchmark datasets [77] to verify the three strategies we proposed in this paper. Results show that compared to the baseline model POMO*, both our PIP and PIP-D frameworks significantly reduce the infeasibility rate and enhance solution quality.
Table 15: Model performance on the benchmark datasets [77].
POMO*
POMO*
PIP
POMO* + PIP-D
POMO
POMO" + PIP
POMO* + PIP-D
Instance
Opt.
Instance
Obj.
Gup
Obj.
Gap
Obj.
Gap
Obj
Gap
Obj.
Gap
Obj.
Gap
20.001
380
2.91%
2,91%
040
4.64%
497
4.85%
m20w20.002
286
292
2.10%
2.10%
m40w-40:000
452
n20w 120w20.009 20.003
394
1
1
m40w-40 005
453
470
3.75%
471
3.97%
k20w 20.004
396
405
2.3%
405
2.27%
405
2.27%
B40w600001
494
525
6.28%
n20w 20.005
352
360
2.27%
560
2,27%
640 002
470
502
681%
n20w30.000
254
276
8.66%
9.84%
840w601003
k00w40.007
640w600004
9.95%
=20w400.00
332
4.73%
4.78%
840w500005
2.4%
4.88%
220w10.000
388
401
3.35%
3.35%
m/0w:80.001
407
3.04%
107
3.1%%
4200300.005
288
314
9.0%
294
2.00%
302
4,8646
840w9900022
431
448
3.94%
452
4.7%
n20w 60.001
335
377
12.5%
349
4.18%
353
5.37%
B40W900003
412
447
8.5%
414
7.77%
454
10.19%
n20w660.00 6011
244
252
3,29%
260
6.56%
040g800 004
417
450
3.12%
435
4 4.32%
k20w60.003 003
352
369
4.8%
358
1.70%
358
1,708
n4Dw800.00 00.
344
390
13.4%
362
5.238
379
10.17%
620w600.044
208
n60w/800001
620w60.005
6.80%
260w90
540
10.04%
n20w80
329
5.8%
347
5.47%
5.47%
n60w:50.00 003
550
635
15.45%
616
17.4%%
820w80.001
338
350
15.4%
347
2.666
366)
6,51%
160
366
611
7.95%
632
11.60%
120w80.005
320
361
12.8%
378
2.50%
328
2,508
n60w90 005
468
535
14.32%
020w80.000 00.004
304
339
11.5%
341
12.
399
11.515
08D
554
582
5,05%
k20w80 005
264
312
18.2%
302
14.39%
302
14,39%
n80w80.002
633
678
7.11%
20.001
500
180W901004
678
9.53%6
20.020.002
10.51%
#40 20.003
6.07%
080x800001
240.20.004
404
419
3.71%
418
3.47%
280w501002
592
624
5.1%
638
7.77%
n4Ow 20.005
499
7
880w800 003
580
648
10.02%
674
14.45%
10,00
465
7
180w550.004
594
674
13.47%
676
13.80%
nl0ww10.002
461
485
5.21%
483
4,77%
n80w890.005
570
627
10.00%
Average Gap
9.8%
5.2%
5.3%
Average Cap
8.10%
7.44%
8.50%
Infensible 4
63.0%
22.2%
14.8%
Infeusible%
53.89%
25.93%
37.04%
E
Broader impacts
This paper focuses on real-world scenarios and proposes novel Proactive Infeasibility Prevention (PIP) framework to enhance the capabilities of neural methods towards solving more complex VRPs. Potential positive societal impacts include: 1) enhancing industrial efficiency, e.g., in logistics and transportation. By preemptively identifying infeasible solutions, it can reduce computational overheads and improve the efficiency of decision-making process; 2) advancing the Al and operation research (OR) communities. Our PIP framework aims to alleviate the existing challenges in the neural VRP solvers, thereby promoting the advancement of Al as well as OR. On the other hand, negative socictal impacts may include environmental unfriendliness due computational resource usage.
24

---

Licenses for existing assets
The used assets in this work are listed in Table 16, which are all open-source for academic research.
We will release our source code with the MIT License.
Table 16: Used assets, licenses, and their usage.
Type
Asset
License
Usage
1.HH3 [71]
Available for academic
Evaluation
OR: Tools [72]
Apache-2.0 license
Evaluation
Code
AM [4]
MIT License
Revision
POMO [5]
MIT License
Revision
GFACS [10)
MIT License
Revision
Datasets
Dumas et al. [77]
Available for academic use
Evaluation
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Please see abstract and Section I, which accurately reflect the paper's contribu- tions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of this work are discussed in Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
26

---

Justification:
This paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibiliyy
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The paper fully discloses the information needed to reproduce the main experimental results in Section and Appendix C.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
27

---

Answer: [Yes]
The source code and data are publicly released with the MIT License in https://github. Deleeybbi/IP-conssreee
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (uttps://nips. ec/
ooiccyyyyy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/ mublic/guidess Caleee//ooSSubbieece bobbmmmsssinn ssisssoliccyyyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The training and test details are presented in Section 5 and Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We validate the statistical significance of experiments Appendix D.6.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
28

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The information on the computer resources is reported in Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https https://ttss////e /tte:://neuurrpe http://s....p.bbciecccheeeeeeeee
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The potential positive societal impacts and negative societal impacts of this work are discussed in Appendix E.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
29

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Licenses for existing assets are detailed in Appendix F.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
30

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The source code and data publicly released with the MIT License in with detailed documentations.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "pWhm7SWfpv", "reviewer": "Reviewer_azSu", "summary": "This paper proposes a Proactive Infeasibility Prevention (PIP) framework to enhance the ability of neural methods to handle complex constraints in Vehicle Routing Problem (VRP).\nThe PIP framework integrates the Lagrangian multiplier to enhance constraint awareness and introduces preventative infeasibility masking to proactively guide the solution construction process. Additionally, an extended version called PIP-D employs an auxiliary decoder and two adaptive strategies to learn and predict masking information, reducing computational costs during training.\nThese methods were extensively tested on different levels of constraint hardness in the Traveling Salesman Problem with Time Window (TSPTW) and Traveling Salesman Problem with Draft Limit (TSPDL) variants. The results demonstrate that the proposed methods enhance the capabilities of neural methods, significantly reducing infeasibility rates and improving solution quality.", "questions": "- Can the proposed idea be applied to methods other than constructive methods? If it can be used to guide the search to avoid infeasibility, it would be a more practical idea.\n- Alternatively, after the (possibly infeasible) solution constructed by a constructive method, is it easy to recover a feasibility through neighborhood search? If so, can you compare this with the avoidance of infeasibility using PIP?\n- Is the model constructed with PIP tailored to the training dataset? In other words, when using the model constructed with PIP for instances in different area, does the number of infeasible instances decrease compared to the model without PIP?\n- Is it possible to use the PIP framework for more general VRP (e.g., with multiple vehicles or capacity constraints)?\n- Are there any experimental comparisons between the proposed model and LKH3 with time limit?", "limitations": "The limitations of this work are discussed in the last section.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tAdaptability to Complex Constraints: The paper devises a method to apply machine learning to constraint-based problems, which have been challenging to handle with deep learning due to the difficulty in finding feasible solutions. \n2.\tExperimental Validation: Experimental results demonstrate that the proposed method can compute feasible solutions more effectively compared to traditional methods.\n3.\tIntegration with Constructive Methods: The proposed approach can be combined with constructive methods, enhancing its practical applicability and flexibility.", "weaknesses": "1. Generality of the Trained Model: It is unclear whether the trained model generalizes well to unseen instances, raising concerns about its robustness and applicability to different problem settings.\n2. Lack of Theoretical Justification for PIP: The paper does not provide a theoretical justification for the superiority of using the Proactive Infeasibility Prevention (PIP) method, leaving its theoretical advantages unproven.\n3. Lack of Classical methods with time limit: There are no comparison with the classical methods (e.g., LKH3) with a time limit. I am concerned that LKH3 could find \"good\" feasible solutions within a short time (e.g., within 5 minutes).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n**[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.\n\n---\n**[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.\n- **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.  \n- **Regarding theoretical support**, we would like to note that each component of our PIP(-D) does have some theoretical support.  \n  - **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].  \n  - **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). \n\nWe agree with the reviewer that theoretical justification is significant and acknowledge the need for further theoretical development, which we leave as a future work.\n\n---\n**[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`.\n\n---\n**[Can our PIP apply to methods other than constructive methods? (Q1)]** Yes, our PIP can potentially be applied to most NCO methods.\n- **Constructive Methods**: We have validated its effectiveness on both autoregressive (AM, POMO) and non-autoregressive (GFACS) methods.  \n- **Iterative Methods**:  \n  - Our PIP can **provide better initial solutions to enhance search efficiency**, as demonstrated in Table R2 of the attached PDF.  \n  - 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.\n\n---\n**[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.\n\n---\n**[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.\n- **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).  \n- **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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9RbzEKBQP1", "reviewer": "Reviewer_DEtT", "summary": "The paper  propose a novel Proactive Infeasibility Prevention (PIP) framework to advance the capabilities of neural methods towards more complex VRPs, and further investigates the Lagrange multiplier method for soft objective in VRPs, presenting the PIP (& PIP-D) for the hard case where Lagrange multiplier method difficult to find feasible solution. And the experiments show that the PIP is prior to Lagrange multiplier method and has generality to TSPTW and TSPDL.", "questions": "[1]What are the potential challenges and limitations in scaling the PIP method to larger and more complex combinatorial optimization problems?\n\n[2]How can we further optimize or modify the proposed method to reduce computational complexity without sacrificing solution quality or feasibility?", "limitations": "yes", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper contributes to the solution of the soft constraint objectives of VRPs.\nThe author's perspective on the problem is also good; that is, the constraint itself is an NP-hard problem, which was not mentioned in reference [8], and the description of why the constraint itself is NP-hard is very clear, that is, because of the irreversible impact of the first selected node on the selection of subsequent customer nodes.", "weaknesses": "The author's method actually addresses the shortcomings of the Lagrange multiplier method, but it is not mentioned in the Introduction, and the problems raised in the Introduction can actually be solved only using the Lagrange multiplier method.   \nThe method involves complex calculations, particularly when integrating the Lagrangian multiplier and PI masking, which can be computationally intensive​. \nThe paper does not thoroughly address the scalability of the proposed method when applied to extremely large datasets, which may limit its practical application in some real-world scenarios​​.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n**[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.\n\n---\n**[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`.\n\n---\n**[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**.\n- **Complex Constraints**: Our PIP is an **early work** to address the complex constraint handling in VRPs, whose significance is acknowledged by the reviewer.  \n- **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.\n\n---\n**[Potential challenges and limitations in scaling PIP to larger and more complex COPs (Q1)]** \n- **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.  \n- **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.\n\n---\n**[Further trials to reduce the computational complexity (Q2)]** Below strategies can be considered for further accelerating the training and inference of PIP:\n- **Apply sparse strategies to refine PIP calculations:**  \n  - **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).  \n  - **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.  \n- **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`.  \n- **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.  \n- **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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Lc3cuTdGvd", "reviewer": "Reviewer_Xb4p", "summary": "This paper addresses the challenge of predicting feasible solutions for VRPs with complex constraints. It introduces two novel methods to enhance existing algorithms: i) integrating constraints directly into the optimization objective using the Lagrangian Multiplier Approach; ii) PIP framework, which proactively excludes potential nodes during solution prediction to prevent future infeasibility. Besides, a neural decoder PIP-D is proposed to reduce computational complexities.\nExperiments on two VRP variants demonstrates significant advancements in feasible prediction compared to the baselines.", "questions": "- What's the time cost of PIP? Is it $time(POMO^*+PIP)$ - $time(POMO^*)$?\n\n- What are the masking strategies of baselines AM and POMO? Do they only mask visited nodes, ignoring other constraints?\n\n- What is the stopping criteria for each algorithm? I know that running LKH3 for 1 second would often generate almost optimal solutions to TSPs with 100 customers, hence there is no need to run it for 14 hours, as shown in Table 2. I recommend the authors use the same time limit (and usually a few seconds for small-sized TSPs considered in this paper) for each baseline algorithm and even present the progress of the objective value for the best solutions found by each algorithm. This could ensure a fair comparison among them.", "limitations": "The author has discussed the limitations in section 6: one potential limitation is that it may not improve performance on all backbone solvers and all VRP variants.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-structured with a logical flow.\n2. The feasibility issue investigated are critical, and the proposed PIP framework address it well.\n3. Extensive experiments and detailed clarifications are made to demonstrate effectiveness.", "weaknesses": "Major concerns:\n\n- **Computational cost.** From the numerical results, PIP incurs approximately twice the computational time compared to baseline neural solvers (e.g., AM and POMO). Despite attempts to mitigate this by introducing neural decoder PIP-D, the reported results don't exhibit a corresponding reduction in time. The authors may clarify this more.\n\n- **Lack of comparisons** between different step numbers in PIP. The authors only conducted experiments of one-step PIP. It is crucial to include comparisons with different step numbers to assess the impact of the \"looking ahead\" masking strategy. For instance, additional results from zero-step PIP (directly masking nodes violating constraints) and two-step PIP. Here, I emphasize zero-step PIP since its masking strategy differs from the ones of the baseline neural solvers, as I understand it. \n\n- Only two TSP datasets are considered. The paper is titled \"Learning to Handle Complex Constraints for **Vehicle Routing Problems (VRPs)**\", however both datasets are **variants of TSPs**. The key difference between VRPs and TSPs is **capacity constraints**. I would like to see VRPs with various complex constraints (such as time windows, pick-up and delivery, split delivery etc.), otherwise, the authors should change the title and consider more TSP variants. \n\n- Heuristic algorithms for TSPs and VRPs with complex constraints have been well developed (such as LKH3). I do not see that the proposed algorithm outperforms the state-of-the-art heuristic algorithms (not neural algorithms).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n**[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:\n- **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.  \n- **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.  \n- **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.\n\n---\n**[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.\n\n---\n**[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.\n\n---\n**[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`.\n\nTo 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).\n\nRegarding the stopping criteria for each algorithm (i.e., to restrain its runtime):\n- For LKH3, we set a fixed number of max trials following the conventions in NCO;  \n- For neural algorithms, we  \n  - 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; \n  - predefine 100 ants and 10 pheromone iterations for GFACS.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bmlQMoUt71", "reviewer": "Reviewer_Seke", "summary": "This paper introduces a novel framework called Proactive Infeasibility Prevention (PIP) to enhance the capability of neural methods in addressing complex Vehicle Routing Problems (VRPs) with interdependent constraints, such as the Traveling Salesman Problem with Time Window (TSPTW) and TSP with Draft Limit (TSPDL). The authors propose integrating the Lagrangian multiplier method and preventative infeasibility masking into the solution construction process to improve both the feasibility and optimality of solutions. Additionally, an enhanced version, PIP-D, employs an auxiliary decoder to predict infeasibility masks, potentially reducing computational costs during training. The paper presents extensive experiments demonstrating the effectiveness of PIP in reducing infeasible rates and improving solution quality.", "questions": "How does the PIP framework generalize to other VRP variants beyond TSPTW and TSPDL?\n\nCan the authors provide more insights into the computational efficiency of PIP-D, especially regarding its scalability?", "limitations": "The authors have acknowledged some limitations, such as the potential inability of PIP to improve performance on all backbone solvers and VRP variants. However, the paper could benefit from a more detailed discussion on the robustness of the PIP framework when faced with different levels of constraint hardness in real-world scenarios.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The PIP framework represents an innovative approach to integrating constraint awareness and preventative measures within neural VRP solvers.\n\nThe use of an auxiliary decoder for predicting infeasibility masks is a good try.\n\nThe paper provides extensive empirical validation demonstrating the effectiveness of the proposed methods.\n\nThe paper is well-organized and clearly presents the problem, proposed solutions, and experimental results. The use of figures and tables effectively supports the textual content, aiding in the reader's comprehension.", "weaknesses": "The ideas of using the Lagrangian multiplier [1] and preventive mask functions[2] are not new.\n\nThe code is not provided, which limits the reproducibility of the work.\n\nIt's not clear how to obtain the training label of infeasibility mask.  The computation could be expensive to get a global and accurate infeasibility mask.\n\nSome related work from recent AI and OR fields are missing.\n\nThe paper could benefit from additional experiments on a wider range of VRP variants and real-world datasets to further validate the generalizability of the proposed methods.\n\nThe presentation could be improved by providing more context on how this work relates to and advances the current state-of-the-art in neural VRP solvers.\n\nThe computational efficiency of the PIP-D framework should be more thoroughly analyzed, especially in terms of how it scales with problem size.\n\nThe paper may lack a deeper discussion on the theoretical underpinnings of the proposed methods and their potential implications for the broader field of combinatorial optimization.\n\n[1] Qiaoyue Tang, Yangzhe Kong, Lemeng Pan, and Choonmeng Lee. Learning to solve soft-constrained vehicle routing problems with lagrangian relaxation. arXiv preprint arXiv:2207.09860, 2022.\n\n[2] Hou, Qingchun, et al. Generalize learned heuristics to solve large-scale vehicle routing problems in real-time. The Eleventh International Conference on Learning Representations. 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n**[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.\n- **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.\n- **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.\n- 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].\n\n---\n**[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.**\n\n---\n**[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.  \n\n---\n**[More literature review]** We have included most recent work from NCO field and will add more from OR field. Any suggestions are warmly welcome!\n\n---\n**[Additional experiments]** \n- 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.\n- 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).\n- 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.\n\n---\n**[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).\n\n---\n**[Computational efficiency]** Please kindly refer to our `General Response #1`.\n\n---\n**[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.\n\n---\n**[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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely appreciate your efforts and insightful comments. We are pleased that reviewers found our PIP(-D) framework to be **novel** (#DEtT, #Seke, #Xb4p), **with** **good perspective** (#DEtT), **practical applicability** (#azSu), **and** **effectiveness in addressing the critical constraint handling problem** (#azSu, #Xb4p). We also appreciate the positive feedback, where reviewers found our paper **logically clear** (#DEtT, #Xb4p, #Seke) and our experiments with various baselines **extensive** (#azSu, #Xb4p, #Seke). In this global response, we address the common concerns.  

---
**[Computational cost and scalability]** Reviewers #DEtT, #Xb4p and #Seke raised questions regarding the computational cost and scalability. While we acknowledge that our framework introduces some unavoidable overhead to the backbone model, we believe it is acceptable for the following reasons:
- **The overhead is actually offset by its strong effectiveness.** Following the reviewer’s suggestion, we show that baselines (POMO and AM) struggle to solve the studied complex constrained VRP, even with prolonged runtimes similar to ours. To see this, we gather additional results in **Table R1** of the attached PDF and show that: 1) Incorporating Lagrangian multiplier (POMO* and AM*) may lead to some improvement (in Table 1 and 2 of main paper) but not for the cases in Table R1 under complex constraints and larger scales; 2) **Even with extended inference time** (by sampling more solutions and data augmentation)**, existing methods do not deliver any feasible solutions;** 3) In contrast, our PIP-D with 48s time, significantly reduces infeasibility from 100% to 6.48% compared to baselines running for 2.5m, and exhibits a optimality gap around only 0.3%. Furthermore, PIP can perform even better with more inference time.
- **We explored several efficient strategies to reduce computational costs in the new PDF, the main paper, and Appendix D.3 and D.4.** These efforts provide a more detailed discussion, and we will follow the comments to better clarify our discussion in the new paper. Below, we summarize them.
  - **1) One-step PI Masking**: Instead of simulating all future possibilities, we use one-step PI masking to approximate NP-hard feasibility mask and reduce computational cost (see new Table R3, R4 and our response `[PIP with different step numbers]` to Reviewer #Xb4p).  
  - **2) Auxiliary Decoder (PIP-D)**: To reduce intensive PI masking calculations, we use an auxiliary decoder to predict one-step PI masking, enhancing training efficiency by 1.5x compared to PIP, especially as scale and constraint complexity increase (see Table 1 and lines 293-296 of the original paper).  
  - **3) Sparse Strategy**: We incorporate sparse strategy (selecting top K neighbours) to handle large-scale problems more efficiently. For GFACS with $n=500$, 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.  
  - **4) Other strategies**: We also enriched the discussion for future work (kindly refer to our response `[Further trials to reduce the computational complexity]` to Reviewer #DEtT for details).
- **Lastly, we believe scalability for larger-scale and applicability to more complex real-world constrained VRPs represent both important directions in NCO.** While our primary focus is more on the latter in this paper, our PIP is an early work to enable backbone models to tackle complex constrained VRPs where masking is NP-hard. Moreover, our PIP is generic and can enhance a wide range of NCO models, as demonstrated with both autoregressive (AM, POMO) and non-autoregressive (GFACS) models in our experiments. As the scalability of the backbone model increases, our PIP framework will also improve.

---
**[Enhanced comparison between PIP and LKH3]** We thank the reviewers (#Xb4p and #azSu) for the insightful suggestions. Previously, we used LKH3 with default settings, and we now compare our PIP(-D) and LKH3 with various time limits (from 5s to 3m per instance) for comprehensiveness. Please refer to Table R2, Figures R2 and R3 in the attached PDF, **where our PIP indeed outperforms LKH3**. We will include these discussions in the revised paper. Below, we summarize the key results.
- **When given a limited budget (i.e., a few seconds, as mentioned by Reviewer #Xb4p), 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.  
- **PIP achieves state-of-the-art performance by further coupling with LKH3.** To leverage the strengths of both approaches, we used our PIP-D to provide better initial solutions for LKH3. This combination reduced the infeasibility rate from 53.11% to 0.21% and improved 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).  
- We also show the progress of objective value and infeasibility rate over inference times in Figures R2, R3 for clearer comparison.

---
**[Additional experiments]** We have conducted additional experiments in the attached PDF, which are summarized below.
* **Table R1:** Results of POMO models under various inference time.  
* **Table R2:** Results of LKH3 and POMO*+PIP-D under various time limits.  
* **Table R3, R4:** Results of PIP with different steps on two datasets.  
* **Figure R1:** Results on VRPBLTW.  
* **Figures R2, R3:** Progress curves of objectives and infeasibility rates over different inference time

Meta-review: This paper introduces and analyzes a  Proactive Infeasibility Prevention (PIP) framework increasing the number of feasible solutions generated when solving complex VRPs, ultimately leading to better quality final solutions found. The paper has several strengths - the problem addressed is an important one, the PIP approach is novel, and a comprehensive experimental analysis (including the generation of several sets of new results during the rebuttal discussion period) demonstrate the advantage of the approach in dealing with VRP/TSP problems with complex constraints. Finally the paper is well-written and understandable.

There were two main perceived weaknesses of the paper. First, was the fact that the proposed method incurs significantly more computational expense  than previous approaches to addressing this problem. Given this fact, there were concerns that some of the experimental analyses that were performed did not adequately make a fair comparison against prior existing approaches.   These concerns led to the addition of several new sets of experiments during the author rebuttal period, which clarified and further highlighted PIP's ability to outperform existing approaches in solution quality, and also showed the ability to further boost solution quality when used in combination. A second observed weakness was the lack of any theoretical model justifying the PIP approach. Subsequent discussion here pointed out that component elements of the approach (e.g., use of Lagrangian relaxation) did have theoretical justification, and consensus was reached that development of a theoretical basis was an important area for future research. Please address all original reviewer concerns and  incorporate all of these new results in the final version of the paper.
Decision: Accept (poster)