acceptodds
Under review as a conference paper at ICLR 2027

Towards Zero-Shot Neural Routing via Constraint Consequence Representation

Abstract

Extending classical solvers for Vehicle Routing Problems (VRPs) to new constraints often requires tailored designs of solver components. While recent neural routing generalists reuse decision rules across variants, their learned representations typically remain tied to predefined constraint types. To enable zero-shot generalization to new constraints, we propose Constraint Consequence REpresentation (CoRE). Motivated by resource extension in classical labeling algorithms, CoRE expresses every constraint through its candidate-level consequences in one shared space, in which a learned heuristic is reused on new constraints without fine-tuning. We integrate this representation into a framework in which one learned scorer guides both construction and refinement. Experiments on 110 VRP variants demonstrate that our model, trained solely on small-scale instances, generalizes effectively to unseen constraint combinations, new constraints, varying constraint hardness, and large-scale instances. CoRE achieves a mean reference gap of 3.68% across 110 routing variants, with a substantial improvement over state-of-the-art neural methods and over prior constraint representations within the same framework. We further show that consequences keep preferred candidates feasible, leading to improved quality, and that our representation serves as a generic module that enhances autoregressive construction and extends to node-oriented problems.

Primary area:
optimization
Keywords:
Vehicle Routing Problems, Zero-shot Generalization, Constraint Representation, Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_f9x6OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper introduces CoRE, a shared representation of simulated constraint consequences, to enable zero‑shot generalization in neural routing solvers. We embed CoRE within a Guided Construction and Refinement (GCR) framework, where a single learned edge‑cost scorer drives both the construction and refinement phases. Experiments across 110 Vehicle Routing Problem (VRP) variants demonstrate that CoRE generalizes robustly to unseen combinations of constraints, entirely new constraints, and large‑scale instances.

Critical strengths
  1. By describing constraints through their consequences rather than fixed attributes, CoRE allows the model to handle new types of constraints without changing or fine-tuning parameters. This makes the approach more flexible.
  2. The GNN-based framework shares learned edge scores between construction and refinement, providing a useful way to combine neural predictions with local search.
Critical weaknesses
  1. The refinement procedure is not explained clearly enough. Although Appendix C.2 lists the local search operators and describes how moves are evaluated, it is still unclear how the sampled perturbation edges are used to define the search region and how the operators are applied within that region. More details would make the method easier to understand and reproduce.
  2. CoRE is trained on 22 VRP variants and also uses local search. The CoRE-UDR controls are useful, but the paper does not report results for GCR without refinement or for constructive baselines with similar local search. This makes it hard to tell how much of the gain comes from the representation, broader training coverage, or refinement.

Despite the impressive results, I remain unsure how much of the improvement is attributable to the proposed representation, and several methodological details remain unclear, making it difficult for me to support acceptance at this stage.

Questions for authors
  1. Could the authors explain more clearly how the sampled perturbation edges determine the local search region and how the different local search operators are applied?
  2. Could the author report the results of CoRE-GCR without refinement, as well as the results of the baselines under the same local search and a similar inference budget?
  3. Could the authors also compare baselines under the same training variants and comparable training budgets? This would help make the comparison more convincing.
  4. Since construction and refinement share learned edge scores, why use PPO to optimize only refinement perturbations instead of training both stages jointly?
4 comments
AuthorsOpenReview ↗

Response to Reviewer f9x6 (1/3)

We sincerely thank the reviewer for the valuable feedback, and for acknowledging that our method handles new constraints without fine-tuning, with impressive results. Please see our response below.

[W1/Q1 - Search region and operators] Sorry for the confusion. Appendix C.2 lists the operators without walking through how they are applied, so we give the complete procedure below. GCR follows Iterated Local Search: construction gives the initial solution, and each iteration runs 10 rollouts from the incumbent, each with four steps guided by the learned cost c^θ\widehat c_\theta of Eq. (5).

  1. Perturbation (where to search). A rollout picks a random customer as the anchor and orders its K=64 candidates by −β,c^θ(e)-\beta\\,\widehat c_\theta(e). In that order, it applies the first feasible move: pulling a segment of 1-3 nodes behind the anchor, splitting the route at the anchor, or inserting an unserved customer. The chosen customer becomes the next anchor (a random unused one if no move applies), until 8 edges differ from the incumbent or 64 attempts are used.
  2. Search region. The region is every customer at an end of a changed edge, so the search stays around the decisions that the learned cost just changed.
  3. Descent (what to do there). The customers of the region form a queue. Each proposes every operator on its K lowest-cost candidates and applies the feasible improving move with the lowest learned cost. The operators are relocate, Or-opt, segment exchange, swap, 2-opt*, 2-opt and paired pickup-delivery relocation, with insertion, removal and replacement moves for optional customers and for depots. If nothing improves, it may accept a move that lowers the learned cost, up to 10 per refinement. Customers touched by an applied move rejoin the queue, until it empties.
  4. Acceptance. The best solution across the rollouts replaces the incumbent only if it lowers the objective.

We gave this as an algorithm in Appendix C.2 of the revision.

AuthorsOpenReview ↗

Response to Reviewer f9x6 (2/3)

[W2/Q2 - Refinement, and baselines with the same local search] We noted that our GCR application is designed to constraint-conditionally guide the fixed local search to any new constraints (please see our response to Reviewer 9gU4, W1). Thus, additionally we trained a "heatmap greedy" model, with the same GNN architecture, and report both results.

Pretrained method without refinement. One greedy pass of CoRE-GCR's construction reaches a 50.11% gap on all 110 variants, against 54.89% with travel distance in place of c^θ\widehat c_\theta. Unlike a heatmap of edges likely to be optimal, c^θ\widehat c_\theta ranks the moves of expert-designed local search, and GCR recomputes it whenever refinement improves the incumbent. The start therefore matters little: on the new constraint sets, URS's solutions start 23 points closer to the reference than this pass (25.35% against 48.76%), yet the same guided search ends within 0.6 points from either (5.23% against 5.83%, second table below).

Heatmap-based non-refinement training. As noted, our CoRE-GCR was designed and trained to guide and transfer the fixed refinement operators. To test consequences in the construction-only scenario alone, we train a heatmap on CVRPBLTW (25,600 instances) and evaluate it in the setting of Table 1. A GNN scores each edge once per instance, and each step CoRE-Heatmap adds the consequence bias bθ(e)b_\theta(e) of Section 4.4, computed from the checks that the feasibility mask already runs on the current candidates, so decoding costs O(PNK∣R∣)O(PNK|\mathcal R|) for PP starts, NN steps and KK candidates, the same order as in masked heatmap decoding instead of attention over all nodes as in autoregressive decoder. UDR-Heatmap instead reads the attributes and live state. Each solution is the best of 100 greedy starts:

MethodObj. ↓Gap ↓Time ↓
URS26.08610.47%48s
RF-POMO28.97122.69%45s
MVMoE29.87926.53%64s
UDR-Heatmap34.28645.20%12s
CoRE-Heatmap29.82226.29%21s

Results show that:

  • Without refinement, CoRE-Heatmap reaches the level of the released constructive generalists in less time (26.29% in 21 s, against 26.53% in 64 s for MVMoE).
  • This level depends on the consequences. With attributes, the model sees each customer's attributes and a shared live state, but not how each move would change that state. Consequences add each candidate's margin to its score, the path that also carries the effect in CoRE-POMO* (please see our response to Reviewer UUvF, Q4).

Same local search. Since URS can supply GCR's initial solution, we start our search from it, guided by travel distance (URS+LS) or by c^θ\widehat c_\theta (URS+CoRE-GCR). The same two guides also run from CoRE-GCR's construction (CoRE+LS, CoRE-GCR), beside Distance GCR, and we tested this on the 40 new constraint sets:

MethodObj. ↓Gap ↓Time ↓
URS11.31325.35%23s
URS+LS9.8327.09%33s
URS+CoRE-GCR9.6925.23%41s
Distance GCR9.9508.28%17s
CoRE+LS9.8767.27%8.6s
CoRE-GCR9.7535.83%25s

Results show that the guidance carries most of the learned gain:

  • On the new constraint sets, it lowers the gap by 1.86 points from URS's solutions and by 1.44 points from CoRE-GCR's construction, whichever construction starts the search.
  • On the 98 variants with a distance objective, the learned construction lowers the gap from 5.86% to 5.42%, and the guidance lowers it further to 4.16%.

In short, under the same refinement, consequences lower the gap by 0.81 points over attributes (4.49% to 3.68% on all 110 variants); without refinement, they take a heatmap from 45.20% to 26.29%; and broader training coverage accounts for at most 0.4 points (Q3 below).

AuthorsOpenReview ↗

Response to Reviewer f9x6 (3/3)

[Q3 - Same training variants and comparable budgets] To clarify this, we match URS's training in the direction that is harder for us: we retrain CoRE-GCR and UDR-GCR (CoRE-UDR in the paper) on URS's 11 tasks, so that route limits, ordered backhauls and multiple depots all become new to them.

VariantURSCoRE-GCR (11)UDR-GCR (11)CoRE-GCR (22)
CVRP1.14%2.52%2.72%1.93%
CVRPL1.06%1.94%2.44%1.57%
CVRPBP13.73%2.77%3.39%2.08%
CVRPTW4.43%3.87%4.46%3.80%
URS's 11 tasks-1.47%0.70%1.15%0.09%
Other 99 variants23.62%4.44%5.49%4.08%
All 110 variants21.11%4.06%5.05%3.68%

Results show that training coverage explains little of the gain:

  • On the 99 variants URS never trained on, CoRE-GCR trained on URS's 11 tasks stays within 0.4 points of our 22-task model, far below URS and below UDR-GCR trained on the same tasks. On URS's own tasks, URS remains lower.
  • The training budgets remain unequal, in URS's favour: URS keeps its published 1,000,000 batches of 128 (about 95 hours on an RTX 4090), while CoRE-GCR trains on 5,000 instances (2.6 hours on an A100).

[Q4 - Why PPO only on refinement?] We clarify that this is an empirical choice rather than a derived one: construction reads the same learned cost c^θ\widehat c_\theta but lies outside the PPO batch, because training on it gave worse results. To analyze this, we retrain CoRE-GCR with both stages trained jointly:

MethodObj. ↓Gap ↓
CoRE-GCR (joint PPO, retrained)8.6144.14%
CoRE-GCR (retrained)8.6013.82%

Results show that joint training raises the gap on every population: from 0.82% to 1.10% on the training variants, from 4.53% to 4.86% held-out, and from 6.06% to 6.52% on the new constraint sets. We attribute this to the same observation in prior works that also trained on local searched tour, e.g. NLS in DeepACO (Ye el. al), and SRR in DyNACO (Tran et. al.), thus keeping the rollout's reward attributable to the choices that produced it.

We included those additional results in the revised paper. Hope these help address your remaining questions/concerns.

Thank you for the clarifications and additional experiments. They address some methodological questions, but my concern about performance attribution remains.

  1. Although CoRE-GCR is retrained on URS’s 11 tasks, the comparison still uses URS without refinement and CoRE-GCR with refinement, leaving CoRE-GCR’s advantage unclear.
  2. CoRE-GCR achieves a lower gap than CoRE+LS but takes 25s versus 8.6s. A comparison under a similar inference budget is therefore needed to establish the benefit of using the learned cost to guide the same local search.
  3. The authors also acknowledge that one greedy pass of CoRE-GCR’s construction performs substantially worse than URS, suggesting no clear advantage of the proposed method over existing baselines.
  4. Starting refinement from URS’s solutions yields better results than the original CoRE-GCR method. This further suggests that the performance gain mainly comes from refinement rather than the proposed model itself.

Therefore, I remain unsure how much of the improvement is attributable to the proposed representation and maintain my original score.

Reviewer_UUvFOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper proposes Constraint Consequence Representation (CoRE) for transferring learned routing heuristics across constraint combinations and previously unseen constraints. Each candidate–constraint pair is represented by normalized current and successor states, a feasibility grade, and a reset indicator. Shared neural mappings encode these representations to guide construction and refinement. The paper also integrates CoRE into POMO* and separately trained graph optimization policies. The idea is promising, and the experimental coverage is broad. However, the main presentation leaves important architectural choices unclear, while questions about heterogeneous constraint representations, comparison fairness, and computational overhead remain insufficiently resolved.

Critical strengths

The problem is important and the proposed interface between constraint handling and learned guidance is useful.

Critical weaknesses
  1. The model architecture is insufficiently explicit. The description does not clearly specify the complete computational paths, dimensions, and parameter sharing of the added context and bias modules, or how context enters the original decoder. I haven't gained a big-picture understanding of how the new method works.

  2. The robustness of shared encoding across heterogeneous constraint semantics remains unclear. Numerical slack, ordering requirements, set-valued states, and compatibility relations can have different implications for future decisions. The successful new-constraint experiments support transfer, but do not isolate sensitivity to how these different semantics are compressed into the shared representation. A targeted comparison of alternative encodings would help characterize this sensitivity. The acknowledged need for manual definitions does not by itself resolve this issue. I am not convinced that it is reasonable to handle constraints—which involve vastly different effects and implications—using shared parameters.

Questions for authors
  1. What is the complete forward-pass specification for CoRE-POMO*, in the view of model architecture, including tensor dimensions, learnable mappings, parameter sharing, context injection, and the precise changes from POMO*?

  2. What evidence supports the transferability of the shared scoring mechanism across numerical, ordering, set-valued, and relational constraints?

  3. Can CoRE and URS be compared under matched training-task coverage and explicitly aligned constraint semantics? How do solution quality and feasibility compare under strictly matched inference-time budgets?

  4. Can the authors report context-only, bias-only, and combined AR ablations, together with runtime and peak-memory breakdowns? Measurements across instance sizes and numbers of active constraints would clarify the additional computational cost.

4 comments
AuthorsOpenReview ↗

Response to Reviewer UUvF (1/3)

We sincerely thank the reviewer for the constructive and valuable feedback, and for acknowledging that our idea is promising and our experimental coverage is broad. Please see our response below.

[W1/Q1 - Forward pass of CoRE-POMO*] We are very sorry for the confusion. CoRE-POMO* keeps POMO*'s encoder and changes two terms of its decoder: in the query q\mathbf q, the consequence context cθ\mathbf c_\theta replaces the attributes (load, time, length), and the content logit ℓψ\ell_\psi of each candidate ee gains the consequence bias bθ(e)b_\theta(e):

POMO*:q=Wq[hlast,(load,time,length)],p=softmax⁡e[ℓψ+M],CoRE-POMO*:q=Wq[hlast,cθ],p=softmax⁡e[ℓψ+bθ(e)+M].\begin{aligned}\text{POMO*:}\quad&\mathbf q=W_q[\mathbf h_{\mathrm{last}},(\text{load},\text{time},\text{length})],&&p=\operatorname{softmax}_e[\ell_\psi+M],\\\\\text{CoRE-POMO*:}\quad&\mathbf q=W_q[\mathbf h_{\mathrm{last}},\mathbf c_\theta],&&p=\operatorname{softmax}_e[\ell_\psi+b_\theta(e)+M].\end{aligned}

Both new terms are recomputed after each selection, in three steps.

1. Simulate. The environment simulates every candidate ee under every active constraint rr and returns its consequence vector of Eq. (2), with no parameters:

ur(e)=(x~r,x~r,e′,gr,e,qr,e).\mathbf u_r(e)=\bigl(\widetilde x_r,\\ \widetilde x'_{r,e},\\ g_{r,e},\\ q_{r,e}\bigr).

2. Context. A shared MLP ϕθt\phi^{t}_\theta summarizes each constraint rr into a token tr\mathbf t_r, from its current state and how the open candidates LL would change it, Δr,e=x~r,e′−x~r\Delta_{r,e}=\widetilde x'_{r,e}-\widetilde x_r. Sum-pooling the tokens over the constraints, as in Eq. (3), gives cθ\mathbf c_\theta, of the same size as (load, time, length):

tr=ϕθt(x~r,mean⁡e∈LΔr,e,max⁡e∈LΔr,e)∈R16,cθ=ρθc(Pool⁡r∈Rtr)∈R3.\mathbf t_r=\phi^{t}_\theta\bigl(\widetilde x_r,\\ \operatorname*{mean}_{e\in L}\Delta_{r,e},\\ \max_{e\in L}\Delta_{r,e}\bigr)\in\mathbb R^{16},\qquad \mathbf c_\theta=\rho^{c}_\theta\bigl(\operatorname{Pool}_{r\in\mathcal R}\mathbf t_r\bigr)\in\mathbb R^{3}.

3. Bias. The shared MLP ϕθ\phi_\theta of Eq. (3) embeds each vector ur(e)\mathbf u_r(e) into κθ,r(e)\boldsymbol\kappa_{\theta,r}(e), and attention over the tokens gives each constraint a weight λθ,r\lambda_{\theta,r} from the states of all active constraints. Sum-pooling the weighted embeddings in the same way gives bθ(e)b_\theta(e), one score per candidate:

κθ,r(e)=ϕθ(ur(e))∈R16,λθ,r=2σ(14∑s∈RQ(tr)⊤K(ts),x~s+v(tr)),\bθ(e)=10tanh⁡ρθb(Pool⁡r∈Rλθ,r,κθ,r(e)).\begin{aligned}\boldsymbol\kappa_{\theta,r}(e)&=\phi_\theta(\mathbf u_r(e))\in\mathbb R^{16},\\\\\lambda_{\theta,r}&=2\sigma\Bigl(\tfrac14\sum_{s\in\mathcal R}Q(\mathbf t_r)^{\top}K(\mathbf t_s)\\,\widetilde x_s+v(\mathbf t_r)\Bigr),\\\b_\theta(e)&=10\tanh\rho^{b}_\theta\bigl(\operatorname{Pool}_{r\in\mathcal R}\lambda_{\theta,r}\\,\boldsymbol\kappa_{\theta,r}(e)\bigr).\end{aligned}

Finally, the next customer is drawn from pp under POMO*'s visited-node and depot mask MM: sampled during training, and chosen greedily at test time, where the POMO starts keep the best route.

All maps are shared across constraints and see them only through this sum pooling, so the same weights accept any number of constraints in any order. They add 1,941 parameters to POMO*'s 1,254,528 (0.155%). Our response to Q4 below ablates the context and the bias, each alone and combined.

AuthorsOpenReview ↗

Response to Reviewer UUvF (2/3)

[W2/Q2 - Why shared parameters?] We hypothesize that in VRP, especially the unlimited fleet constraint widely used in the literature, every constraint acts on a decision in the same way: a move keeps the solution feasible or forces a repair, which with an unlimited fleet is a detour through the depot. Thus, our interpretation is that the performance and transferability of our design can be attributed to learning how constraints and its consequence affect the (local) feasibility of the route. We clarified this in the revision.

We thank the reviewer for the suggestion on comparing encodings. We retrain the same model on attributes (UDR-GCR, CoRE-UDR in the paper), a constraint prompt (CaDA-GCR, CoRE-CaDA in the paper) and the full consequence vector (CoRE-GCR), with the same training tasks, simulator and search:

MethodBackhaul order (30)Pickup-delivery (3)Time windows (44)Route limits (46)All held-out (89)New constraint sets (40)
UDR-GCR5.76%0.86%7.61%5.14%5.22%6.59%
CaDA-GCR5.62%0.67%7.48%4.98%5.06%6.50%
CoRE-GCR4.88%-0.78%6.76%4.31%4.32%5.76%

We also retrain the steps from the binary mask to the grade gr,eg_{r,e} and the event qr,eq_{r,e}:

MethodAll held-out (89)New constraint sets (40)New constraints (4)
Binary mask5.57%6.92%0.62%
Grade4.77%6.60%0.00%
Grade + event4.52%6.04%-0.04%
CoRE-GCR (retrained)4.53%6.06%-0.10%

Results show that:

  • Consequences lead on every constraint type, ordering (backhaul order, pickup-delivery) and numerical (time windows, route limits), and on the four new constraints, numerical, set-valued and relational (please see our response to Reviewer 9gU4, W1).
  • Along the steps, the grade lowers the gap of the binary mask on all three populations, and with the event added, the model matches the retrained CoRE-GCR.
AuthorsOpenReview ↗

Response to Reviewer UUvF (3/3)

[Q3 - Matched comparison with URS] We clarify that URS is a constructive generalist, while GCR guides a local search. We therefore compare from three sides, and also start our search from URS's solutions (please see our response to Reviewer f9x6, W2/Q2):

  • Training coverage. CoRE-GCR and UDR-GCR share the same 22 training tasks (W2/Q2 above). For CoRE-GCR retrained on URS's own 11 tasks, please see our response to Reviewer f9x6, Q3.
  • Aligned semantics. Every returned solution, URS's included, is checked for feasibility under the same constraint definitions, those of URS's 110 variants, and its cost is recomputed on one objective scale (Appendix D.1).
  • Matched time. CoRE-GCR takes 0.235 s per instance and URS 0.508 s. Given at least CoRE-GCR's time on every variant, URS reaches 21.11% against 3.68% for CoRE-GCR. At N=1000, on the 91 variants where both complete, CoRE-GCR takes 7.11 s per instance and URS 10.86 s, with gaps of 6.70% against 17.46%.

[Q4 - AR ablations, runtime and memory] To further clarify AR performance, we ablate the two paths in CoRE-POMO*, where no search can undo a decision: POMO* (context) replaces the attribute context with cθ\mathbf c_\theta, and POMO* (bias) keeps it and adds bθ(e)b_\theta(e). A full training takes 75 to 117 hours, so these models stop at 400,000 training instances, by which point the full models have already separated. Due to the short rebuttal window, we will include the full runs in the camera-ready version.

MethodGap ↓Infsb% ↓
POMO*28.12%61.9%
POMO* (context)28.86%57.8%
POMO* (bias)14.08%11.7%
CoRE-POMO*13.70%2.5%

VRPBLTW, N=50: 128 validation instances after 400,000 training instances.

Results show that the bias carries the effect: alone, it halves POMO*'s gap, while the context alone stays at POMO*'s level. Alongside the bias, the context lowers infeasibility from 11.7% to 2.5%.

For runtime and peak memory, we measure both models per instance on one RX 6800, with the batch size falling as N grows:

N (batch)POMO* time (ms)CoRE-POMO* time (ms)POMO* memory (GB)CoRE-POMO* memory (GB)
50 (256)9.130.11.013.11
100 (64)17.7131.80.853.09
200 (16)63.8645.00.611.93
500 (2)342.71924.20.400.63
  • At N=100, valuing the consequence vectors takes 58% of CoRE-POMO*'s time, and simulating them 11%.
  • From one to three active constraints, its time per instance stays between 121 and 132 ms, with peak memory at 3.1 GB.

For the same measurements on GCR, please see our response to Reviewer 9gU4, Q6.

We included those additional results in the revised paper. Hope these help address your remaining questions/concerns!

Thank you for the clarifications and additional experiments, which address some of my concerns and strengthen the empirical evidence. I still have some concerns:

  1. The current results of AR ablations may reflect faster early learning rather than better final performance. Full results are needed to convince me about the modules’ contributions.
  2. At N=1000, what are the completion and feasibility rates across all 110 variants, including those outside the 91-variant common subset? Restricting the comparison to jointly completed variants may obscure differences in overall reliability.

Although the time is limited, which I understand, I believe above results are very helpful to support the claims of the paper. I will also accept sound argumentation that can justify the above points.

Reviewer_9gU4OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Constraint Consequence Representation (CoRE), a representation for enabling neural routing models to generalize to unseen constraint combinations and entirely new constraint types without fine-tuning. The central idea is to represent each constraint through the consequences of a candidate move, including the normalized constraint state before and after the move, a feasibility margin, and a reset-event indicator. These representations are processed by shared neural networks, allowing new constraints to be incorporated without adding constraint-specific learned parameters. The authors integrate CoRE into a Guided Construction and Refinement (GCR) framework and evaluate it on 110 VRP variants, including held-out constraint combinations, four constraints absent from training, and instances with up to 1,000 customers. They also investigate integration with POMO and extensions to node-oriented combinatorial optimization problems.

Critical strengths
  1. The paper identifies a meaningful limitation of existing neural routing generalists: they can transfer across combinations of predefined constraints but may require architectural changes or additional training to accommodate entirely new constraint types. Addressing this limitation could improve the adaptability and extensibility of neural optimization solvers.

  2. CoRE represents constraints through candidate-level state transitions, feasibility margins, and reset events. This provides richer information than a binary feasibility mask and allows heterogeneous constraints to be processed using shared neural parameters. The approach separates constraint enforcement from the learned heuristic.

Critical weaknesses

The core idea of CoRE is to encode constraint-specific state transitions and feasibility margins into a shared representation. However, resource states, transition functions, and feasibility checks are already fundamental components of classical resource-constrained shortest-path and vehicle-routing algorithms. The paper is motivated by these classical methods, but it is not yet sufficiently clear which aspect constitutes the principal methodological advance beyond encoding existing solver states as neural features and sharing an encoder across constraints.

The paper evaluates four constraints absent from training: battery replenishment, destination-dependent draft limits, cluster limits, and route incompatibility. These cover several useful constraint structures, but they do not establish that the representation will generalize broadly to arbitrary new constraints. Importantly, all the constraints still require manually specified transition functions, feasibility checks, normalization rules, and consequence vectors. The learned model therefore transfers to new constraint representations, but the construction of those representations remains problem-specific. The central claim of zero-shot generalization is not convincing.

CoRE is evaluated within GCR, which uses learned construction and refinement, while several competing generalist methods use different architectures and search procedures. The reported improvements may reflect a combination of the consequence representation, the learned cost function, the construction procedure, and the refinement strategy. Their effects however are not isolated.

Questions for authors

The compared methods are trained with the same data? How is the CoRE performance tested using the test data used in other literature? What properties must a new constraint satisfy for its consequence vector to be processed effectively by a pretrained model? Are there examples of constraints for which the representation fails? How much of the improvement over existing neural generalists can be attributed to CoRE itself, rather than to GCR's construction and refinement strategy? What is the runtime overhead of consequence simulation, and how does it scale with the number of constraints and candidate actions?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 9gU4 (1/2)

We sincerely thank the reviewer for the valuable feedback, and for acknowledging that our method addresses a meaningful limitation with richer information than conventional masking. Please see our response below.

[W1 - Novelty beyond classical resource states] Sorry for the confusion. As you noted, states, transitions and checks are classical, and we take them as the simulator computes them. Our contributions are significant in two ways:

  • Conceptually, every constraint acts on a routing decision in the same way: a move keeps the solution feasible or forces a repair, which with an unlimited fleet is a detour through the depot. The consequence vector generalizes the binary mask to how close a candidate comes to that repair (the grade gr,eg_{r,e}), whether the move resets the constraint (the event qr,eq_{r,e}), and the states before and after it, on one scale across constraints.
  • Technically, one pretrained model reads these vectors for any constraint, which we tested for numerical, set-valued and relational constraints alike. A new constraint only adds a term to a sum over constraints, with no new parameter and no fine-tuning.

For the measured gain for the progression from simple binary mask, please see our Table 12 on VRPIC, or our response to Reviewer UUvF (W2/Q2), and W3 below.

We clarify that CoRE is a representation that can be widely applied in two paradigms: Learning-Guided Optimization (LGO, e.g. NeuroLKH, DeepACO, L2Seg), where a learned component guides a classical method (CoRE-GCR), and constructive solvers (CoRE-POMO*). In CoRE-GCR, the learned cost c^θ\widehat c_\theta, conditioned on consequences, lets expert-designed local search (e.g. 2-opt, 2-opt*) transfer not only to new combinations of constraints but to new constraints themselves. To the best of our knowledge, this is the first LGO generalist. Table 16 compares it with single-problem LGO methods (NeuroLKH, DeepACO, DyNACO).

Results below show that, with every learned parameter frozen, CoRE-GCR outperforms OR-Tools at 600 s on EVRP and stays within 0.5% on the other three new constraints in about a minute, while attribute inputs fall behind under the same guided search. We believe this transfer to new constraints is a highly impactful and novel finding.

MethodEVRP Obj. ↓EVRP Gap ↓EVRP Time ↓VRPDL Obj. ↓VRPDL Gap ↓VRPDL Time ↓VRPCL Obj. ↓VRPCL Gap ↓VRPCL Time ↓VRPIC Obj. ↓VRPIC Gap ↓VRPIC Time ↓
OR-Tools15.9880.00%21.3h17.4210.00%21.3h10.4550.00%21.3h17.3160.00%21.3h
UDR-GCR15.927-0.38%25s17.5900.97%25s10.5370.79%21s17.5581.40%34s
CoRE-GCR15.901-0.55%33s17.4920.41%31s10.4790.22%52s17.3270.06%59s

[W2 - Zero-shot and manual definitions] We clarify that zero-shot means that no learned parameter changes and no training happens on the new constraint.

  • A new constraint supplies its transition and feasibility check, as it must to any general constrained solver, and the binary mask is itself a special case of our consequence vector.
  • The grade can reuse the shared numerical form (capacity, duration, length, time). On VRPIC, the case study in Appendix E.2 shows that different definitions all improve on UDR, and that richer information improves on the binary mask (Table 12).

We have clarified this in the revision.

AuthorsOpenReview ↗

Response to Reviewer 9gU4 (2/2)

[W3/Q5 - Attribution] Sorry for the confusion. We isolate these effects within each paradigm, so the rows of each table differ only in their constraint representation.

MethodAll (110)Held-out (89)New constraint sets (40)Time ↓
URS21.11%24.00%23.46%64s
Distance GCR5.44%6.13%7.74%20s
UDR-GCR4.49%5.22%6.59%25s
CoRE-GCR3.68%4.32%5.76%30s
MethodN=50N=50 → 100N=100
POMO* (attributes)1.99%6.56%-1.65%
CoRE-POMO*0.10%2.08%-3.32%

Results show that:

  • On all 110 variants, learned guidance lowers the gap of Distance GCR by 1.76 points, of which consequences give 0.81 points over attributes.
  • The gain is larger where refinement cannot undo a poor choice. Without search, consequences lower POMO*'s gap by 1.7 to 4.5 points. On Short-route packing at Hard, decided at construction, they lower CoRE-GCR's infeasible rate from 99.22% with attributes to 45.31%.
  • The gap to URS is between paradigms, constructive and guided search, rather than a component of our method: with our local search, URS reaches 7.09% on the new constraint sets, still above CoRE-GCR (please see our response to Reviewer f9x6, W2/Q2).

This confirms our core interpretation: consequences let one learned model transfer across constraints.

[Q1 - Same training data?] Training and testing both use the 110-variant benchmark released by URS, collected from AM, MatNet, Heter-AM, MVMoE and MTPOMO. CoRE-GCR trains on 22 tasks and 5,000 instances (Appendix D.1, Table 8). To match URS's training data, we also retrain CoRE-GCR on URS's 11 tasks (please see our response to Reviewer f9x6, Q3).

[Q2 - Test data from other literature] We add two public sets, compared against their best-known solutions: CVRPLIB Set X for CVRP (100 instances, N=100-1000) and the Homberger-Gehring (H-G) benchmark for CVRPTW (12 instances, N=1000). CoRE-GCR has the lowest gap on both.

MethodSet X Obj. ↓Set X Gap ↓Set X Time ↓H-G Obj. ↓H-G Gap ↓H-G Time ↓
URS67683.76.60%108m53528.251.87%57m
Distance GCR65603.94.26%33m47465.535.01%81m
CoRE-GCR65229.83.33%79m45448.427.81%1.9h

[Q3 - Required properties of a new constraint] A new constraint needs three properties:

  • Executable: it supplies a transition and a feasibility check, as any general constrained solver (e.g. OR-Tools, Gurobi) requires.
  • Sufficient: its consequence vector carries what the decision depends on. In short, the optimal local choice cannot depend on some constrained (global) relations, that the local consequence cannot expressed (Appendix B.2). Numerical constraints (capacity, battery) and relational ones (backhaul, pickup) satisfy this.
  • In distribution, which can be checked before solving: 3.5% of CoRE-GCR's inputs fall outside the training range on the new constraint sets, and 8% to 32% on the four new constraints, where CoRE-GCR still transfers (W1).

[Q4 - Failure cases] Theoretically, Appendix B.2 shows that the representation fails when a constraint's feasibility depends on a relation between moves that its current state does not hold: two moves then share a consequence vector yet allow different continuations (Proposition B.1). In the routing variants benchmarked in the literature, feasibility depends only on the route's current state (e.g. load, time, length), so this case does not arise. Empirically, we regard feasibility as the hard case:

  • On Short-route packing at Hard, CoRE-GCR remains infeasible on 45.31% of instances, less than half of URS's 94.53%, while RF-MoE and CCL fail on every instance.
  • Adding a grade reconstruction loss, an MSE on the grade the simulator computes, lowers this rate to 10.16%, at the cost of a higher gap on new constraint sets (Figure 3), so CoRE-GCR keeps it off for transfer.

[Q6 - Runtime of consequence simulation] Simulation adds little, because GCR recomputes the learned cost c^θ\widehat c_\theta only when the incumbent improves, not at every decision:

  • In the run below, it takes under 0.6% of the solve time. It grows with the number of constraints and stays flat in the number of candidates K.
  • In the main evaluation at N=100, CoRE-GCR takes 0.235 s per instance and Distance GCR 0.161 s, so the learned cost adds 0.074 s.
Active constraintsK=16K=32K=64K=128
0 (TSP)1.31.41.51.5
1 (CVRP)4.04.14.04.0
2 (CVRPL)6.26.56.36.3
3 (CVRPLTW)11.011.111.011.0
4 (CVRPBPLTW)11.811.811.811.9

We included those additional results in the revised paper. Hope these help address your remaining questions/concerns.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.