acceptodds
Under review as a conference paper at ICLR 2027

Size Generalization for Diffusion Routing Solvers

Abstract

Routing problems, like the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP), are NP-hard and slow to solve for large instances. Diffusion-based solvers can be trained in a supervised way using sets of optimal solutions, and then quickly solve new test instances. However, for large instances, optimal solutions are hard to find, and diffusion models fail to generalize to instance sizes outside their training distribution. Here we describe ResizeCO, a label-free size-generalization approach that addresses both the change in statistical properties of larger instances, and the computational challenge of solving them quickly. It uses reinforcement learning on large-scale instances to adapt a diffusion model trained on small instances. Specifically, we adapt GRPO to this problem, using route length as the training signal. ResizeCO also formulates k-opt as a tree search, solved by a beam search on the GPU. In size-generalization experiments on TSP and CVRP instances with up to 10000 nodes, ResizeCO achieves a Pareto front over route quality and time that dominates learned solvers, and also outperforms other solvers at short run times, setting a new state of the art.

Primary area:
optimization
Keywords:
Neural Combinatorial Optimization, Large-Scale Vehicle Routing Problem, Size Generalization, Reinforcement Learning, Graph Transformer, Local Search

Reviews

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

This paper proposes ResizeCO, which adapts a diffusion routing solver pretrained on small labeled instances to larger instances through label-free RL at the target size. It combines a Graph Transformer encoder with an MPNN structure extractor, post-2-opt rewards for RL fine-tuning, and GPU beam k-opt search at inference. The authors evaluate ResizeCO on TSP and CVRP instances with up to 10000 nodes, claiming a Pareto advantage over learning-based solvers in route quality and runtime.

Critical strengths
  1. The Graph Transformer encoder combines an MPNN structure extractor with global attention, making attention sensitive to local graph structure while retaining a global view.
  2. The GPU beam k-opt search organizes Lin-Kernighan-style edge exchanges into a parallel beam search and applies compatible moves together, making route improvement better suited to GPU execution.
Critical weaknesses
  1. The title about size generalization overstates what the major experiments establish. The main results primarily demonstrate target-size adaptation rather than zero-shot transfer of a model trained only on small instances.
  2. The claimed GRPO framework requires a more rigorous description. This paper actually adopts group-normalized REINFORCE-style training and sets the KL divergence coefficient to zero during training at a 10K-node scale.
  3. The evaluation omits highly relevant methods DGL and L2R, which are clearly trained only on 100-node instances and aimed at size generalization. Thus, the claim that ResizeCO dominates existing learned solvers is insufficiently supported.
  4. In the main experiment, the authors did not report constructive results without any post-search strategy. It is unclear whether the gains are attributable to improved construction quality or to stronger search.
  5. Although node-walk decoding respects capacity, Appendix B.5 allows GPU beam k-opt to pass through overloaded CVRP solutions without clearly specifying how final feasibility is enforced or reporting final feasibility rates. This makes the CVRP results unconvincing, particularly the negative gaps at size 10000.
Questions for authors
  1. Could the authors evaluate the model trained only at size 100 on large-scale uniformly distributed instances and all TSPLIB/CVRPLIB groups, without any target-size RL?
  2. Could you provide a controlled comparison between ResizeCO's group-standardized advantages and POMO-style mean-centered advantages to clarify whether the additional normalization provides a meaningful benefit?
  3. Given the use of B200/H200 GPUs for large-scale training, could you report peak GPU memory usage across the full training pipeline?
  4. Could you report ResizeCO's results without post-search, and baseline results with the same post-search strategy as ResizeCO?
  5. Could you clarify the CVRP post-search procedure, explain how final feasibility is ensured, and report the feasibility rate?
  6. Could you report the average and maximum numbers of GPU beam k-opt search at each test size for each problem?
7 comments
AuthorsOpenReview ↗

Response to Reviewer Aw3M (1/5)

Thank you for the detailed review. Your comments helped us sharpen the paper: we now show solution quality before and after search, apply our search to the baselines, and report CVRP feasibility.

Critical strengths: We appreciate your recognition of our Graph Transformer, which combines local and global graph information, and GPU beam k-opt, which makes large-instance route refinement efficient.

Question 1: How does the size-100 model perform without target-size RL?

We evaluated the size-100 supervised checkpoint on every reported uniform and real-world group, before and after target-size RL. Both ResizeCO checkpoints use the same decoder and search. MaskCO-100 uses native inference with 2-opt and no beam. Each entry is gap (%) / total time (s per instance).

EvaluationResizeCO (after SL)ResizeCO (after RL)MaskCO-100
TSP-5002.707 / 0.0440.329 / 0.0203.181 / 0.078
TSP-1,0003.231 / 0.0840.813 / 0.0597.268 / 1.836
TSP-10,0004.775 / 2.6194.029 / 2.712347.299 / 116.188
CVRP-5007.445 / 0.2713.176 / 0.1096.850 / 0.113
CVRP-1,0006.698 / 0.9013.426 / 0.2226.038 / 0.184
CVRP-10,0002.531 / 162.011-0.056 / 18.1664.278 / 43.243
EvaluationResizeCO (after SL)ResizeCO (after RL)MaskCO-100
TSPLIB 400–6572.548 / 0.7471.264 / 0.6762.797 / 7.910
TSPLIB 724–1,4323.085 / 1.9431.462 / 1.1666.913 / 4.843
TSPLIB 11,849–14,0515.794 / 12.5464.831 / 10.055397.686 / 95.243
CVRPLIB 321–6845.865 / 1.0183.670 / 0.3746.170 / 1.069
CVRPLIB 748–9565.164 / 2.6633.80 / 0.75.604 / 1.105
CVRPLIB XXL 7,000–15,00011.827 / 158.4319.483 / 32.129855.981 / 39.371

With the decoder and search fixed, RL lowers the gap in every uniform and real-world group. This directly shows a learning benefit from label-free target-size adaptation: the larger instances require no optimal solution labels. The submitted ablations already included comparisons with and without RL; we extended them to all 12 TSP/CVRP source-to-target pairs.

AuthorsOpenReview ↗

Response to Reviewer Aw3M (2/5)

Weakness 1: What do the main size-generalization results establish?

The main results test label-free RL adaptation at the target size. We also test the same model on larger instances without further training, comparing ResizeCO after RL with its starting checkpoint after SL.

The first table reports TSP and the second CVRP. The training-size column gives the supervised source size followed by the RL size; evaluation sizes are larger than the RL size. ResizeCO after SL and after RL use the same decoder, search, and sample count S. Entries are gap (%) / total time (s per instance). SIT uses PRC5/20/3 at 2,000/5,000/10,000 nodes and PRC2/10 at 20,000/50,000 nodes.

EvaluationSL → RL sizeResizeCO after SLResizeCO after RLSIT
TSP-2,000 S=8500 → 1,0002.153 / 3.3900.482 / 1.0581.967 / 1.348
TSP-5,000 S=8500 → 1,0003.437 / 7.6483.133 / 8.4612.542 / 8.364
TSP-10,000 S=1500 → 1,0004.174 / 2.6764.198 / 2.8273.629 / 3.855
TSP-20,000 S=11,000 → 10,0004.985 / 9.633.908 / 8.325.151 / 7.33
TSP-50,000 S=11,000 → 10,00010.867 / 54.0310.140 / 54.045.853 / 64.25
EvaluationSL → RL sizeResizeCO after SLResizeCO after RLMaskCO
CVRP-5,000 S=1500 → 1,0001.525 / 12.2490.926 / 5.9042.985 / 6.95
CVRP-10,000 S=1500 → 1,0000.703 / 67.7240.317 / 31.6787.971 / 29.34
CVRP-20,000 S=11,000 → 10,000-0.016 / 131.7-0.610 / 38.5381.481 / 78.11
CVRP-50,000 S=11,000 → 10,0002.019 / 691.7-0.864 / 498.3863.302 / 194.5 (13/16 feasible)

Beyond the RL size, ResizeCO after RL improves on its after-SL starting point in all four CVRP evaluations and four of five TSP evaluations. It has the lowest gap among the shown methods in every CVRP row and two TSP rows. SIT leads at several TSP sizes, and one TSP row slightly favors after SL. These tests show that adaptation gains often transfer to larger sizes without further training, in addition to our main label-free target-size adaptation claim. We added the results to the paper.

Weakness 4: Do ResizeCO’s gains come from RL, search, or both?

The submitted component ablations test learning and beam refinement separately: Table 5 and Appendix Table D.10 include no-RL and no-beam controls. The no-RL models retain the same search, while the no-beam models retain 2-opt. We extended these ablations to all 12 source-to-target pairs in the paper.

We also compared ResizeCO after RL before any post-search with the full solver on six source-to-target pairs. Within each pair, both versions use the same decoder and sample count. Entries are gap (%) / total time (s per instance).

EvaluationResizeCO (raw construction)ResizeCO (full solver)
TSP-100 → TSP-5004.974 / 0.0090.329 / 0.020
TSP-500 → TSP-1,0003.897 / 0.0280.208 / 0.046
TSP-1,000 → TSP-10,00016.576 / 1.2292.046 / 2.144
CVRP-100 → CVRP-50014.162 / 0.0053.176 / 0.109
CVRP-500 → CVRP-1,00013.725 / 0.0142.764 / 0.198
CVRP-1,000 → CVRP-10,0003.177 / 2.345-0.096 / 18.047

Search lowers the gap in every pair. This is consistent with the RL objective: we train using reward after 2-opt, so the model is trained to produce solutions that improve with search. Q1 answer separately shows that RL helps when decoding and search are fixed. In the matched-time CVRP-1,000→10,000 control of our response to Reviewer 4EkP (Question 1), ResizeCO after RL has lower gaps than after SL both before and after search, at nearly identical total inference time.

AuthorsOpenReview ↗

Response to Reviewer Aw3M (3/5)

Weakness 3: How does ResizeCO compare with DGL and L2R?

We ran their released size-100 models with native inference on our instances, references, and GPU. ResizeCO also begins with size-100 supervision but adds unlabeled target-size RL. DGL uses augmentation ×1, ×1, and ×8 for TSP-500/1,000/10,000 and ×32, ×32, and ×8 for CVRP-500/1,000/10,000; L2R uses greedy decoding. Each entry is gap (%) / total time (s per instance).

EvaluationResizeCODGLL2R
TSP-5000.329 / 0.0204.509 / 0.0234.252 / 0.017
TSP-1,0000.813 / 0.0595.185 / 0.0484.494 / 0.036
TSP-10,0004.029 / 2.7126.463 / 35.0554.745 / 3.406
CVRP-5003.176 / 0.10911.223 / 0.1908.041 / 0.022
CVRP-1,0003.426 / 0.2229.266 / 0.3687.766 / 0.085
CVRP-10,000-0.056 / 18.1662.996 / 48.0512.226 / 4.096

ResizeCO has a lower gap than DGL and L2R in all six settings. L2R is faster on CVRP, but has higher gaps. We also test whether the advantage remains when these baselines receive our search in Q4 below. We added both comparisons to the paper.

Question 4: How does ResizeCO compare when the baselines also use our search?

To test whether ResizeCO’s advantage comes only from its search, we applied GPU beam k-opt to the baseline solutions as well. The table compares the resulting complete TSP solvers, including their construction and refinement time.

DIMES retains active search and MCTS, and DIFUSCO retains its native 2-opt, before our beam search. For MaskCO, our beam search replaces its TSP 2-opt. Total time includes every stage. At TSP-10,000, S=1 gives ResizeCO’s faster setting, while S=16 uses a budget closer to SIT’s. Entries are gap (%) / total time (s per instance).

MethodTSP-500TSP-1,000TSP-10,000
ResizeCO, S=10.329 / 0.0200.208 / 0.0462.046 / 2.144
ResizeCO, S=160.152 / 0.1310.099 / 0.2441.834 / 17.18
DIMES (RL+AS+MCTS) + beam k-opt1.369 / 27.02.121 / 55.72.629 / 458
DIFUSCO (Tₛ=50, S=4) + 2-opt + beam k-opt0.535 / 4.4160.982 / 9.1522.129 / 370.604
SIT (greedy) + beam k-opt1.274 / 0.0811.244 / 0.2081.931 / 17.59
MaskCO (T=16) + beam k-opt1.800 / 0.2010.266 / 0.2513.056 / 19.55
DGL (BS4, aug×32/32/8) + beam k-opt0.922 / 0.7861.270 / 1.0672.157 / 42.709
L2R (greedy) + beam k-opt2.167 / 0.0722.481 / 0.1153.370 / 3.648

ResizeCO has the lowest gap at TSP-500 and TSP-1,000 after the baselines also receive our search. At TSP-10,000, ResizeCO with S=16 beats SIT in gap and total time; S=1 is faster with a slightly higher gap. These comparisons show two benefits: our search also improves baseline solutions, while ResizeCO retains a quality advantage after the baselines receive that search. The gain therefore cannot be explained solely by giving ResizeCO a stronger refinement procedure.

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

This paper proposes ResizeCO, a method for adapting a diffusion-based heatmap solver pretrained on small labeled instances to large-scale TSP and CVRP problems. Built on MaskCO, it incorporates a Graph Transformer encoder and fine-tunes the model on unlabeled target-size instances using a modified GRPO algorithm. Routes are sampled sequentially from the predicted heatmaps through node-walk decoding, enabling exact computation of their log-probabilities under the sampling policy. Rewards are based on negative route costs after 2-opt refinement, and advantages are standardized within each sample group. Where used, a KL penalty over the entire heatmap penalizes deviations from the frozen supervised reference model. At inference, S routes are sampled in parallel, and route refinement uses a GPU beam search over k-opt moves (k ≤ 5), including double-bridge moves. All reported ResizeCO configurations use a single unmasking step and a single correction cycle, with S controlling the computational budget.

Critical strengths

Under the paper’s settings, ResizeCO gives the lowest gap among learned solvers at comparable run times in every main-text setting, and the margin grows with the target size. On CVRP 1000→10000, it reaches −0.096% relative to 4-hour HGS references at about 23 s per instance, against 6.49% for INViT and 7.97% for MaskCO (T=128) (Table 1). On TSP 1000→10000, it reaches 2.05% in 34 s for 16 instances, against 3.04% for SIT and 3.18% for DIFUSCO (Table 3). The ranking largely carries over to TSPLIB and CVRPLIB, with the best learned gap in five of the six groups (Tables 2 and 4). Results are reported as gap–time curves over the full sampling budget with 95% confidence intervals (Figures 3–4), which is more informative than single operating points.

Critical weaknesses

Training a heatmap with policy gradients and sampling tours node by node from it has clear precedent. DIMES (Qiu et al., 2022) samples each next node from the current node's heatmap row, normalized over the unvisited nodes (its Eq. (10)), and trains this policy with REINFORCE directly at TSP-500/1000/10000. With K=1, the setting used in all experiments (Tables B.3–B.4), the node-walk transition of Eq. (2) has the same form, so the exact route probability of contribution (2) is not new in itself. ResizeCO's differences from DIMES lie in its combination of components: supervised pretraining on small labeled instances before RL (DIMES trains from scratch with meta-learning), the Graph Transformer encoder, a reward computed after a 2-opt pass, the policy-gradient objective, and the GPU beam k-opt search at inference. On the objective, each batch receives a single update on fresh rollouts, so the importance ratio is one and PPO clipping never takes effect (App. E); in addition, the KL coefficient is zero at the 10K targets (Table B.3). At the 10K targets, the update therefore reduces to a group-standardized REINFORCE-style gradient without PPO clipping or reference-policy KL regularization, which is close to DIMES's REINFORCE with a sampled-average baseline. Closely related RL + heatmap methods, notably DIMES and CADO (which fine-tunes a supervised diffusion heatmap solver with RL), are mentioned only in Related Work and are not compared, let alone under matched post-processing.

The paper presents ResizeCO as a diffusion solver (title, abstract, contribution (1)), and Figure 1(C) and Sec. 3 describe inference with K unmasking steps and several correction cycles that re-mask and rebuild the route. However, every reported ResizeCO run uses K=1 and C=1, both in RL training and at inference (Sec. 5 "Evaluation Setting", Tables B.3–B.4, App. D.2); only the number of samples S is varied. In these stages, the denoiser is called once on a fully masked input and outputs a single heatmap, so no iterative denoising is performed. The model's ability to complete partial solutions, learned with random masking during pretraining, is not used during RL or inference. The masked-diffusion objective therefore enters only through supervised pretraining, whose parameters are inherited by the later stages. No experiment shows what this random-mask pretraining adds over standard heatmap supervision from a fully masked input with the same architecture.

Questions for authors
  1. RL + heatmap baselines under a matched setting. Please add DIMES and CADO, two particularly relevant prior methods. DIMES trains a heatmap with RL at the target size, and CADO fine-tunes a supervised diffusion heatmap solver with RL. Both report TSP results at the benchmark sizes used here, but please rerun them on the paper's own test instances and hardware. The comparison should use a matched setting: the same access to target-size instances, the same decoder and number of samples, and the same post-processing (either all with 2-opt or all with the GPU beam k-opt). Please report the gap and per-instance time.
  2. What does the masked-diffusion pretraining add? On one representative pair (e.g., TSP-500→TSP-1000), please report two variants. (a) A non-diffusion control: the same architecture, supervised to predict the heatmap from a fully masked input only, followed by the same RL fine-tuning and inference at a matched budget. (b) One multi-step setting (K>1 or C>1, as depicted in Figure 1(C)), compared with ResizeCO at a matched time budget. If K=1 and C=1 remain the best choice, please revise Figure 1(C) and clarify in what sense the method is a diffusion solver.
  3. Zero-shot generalization vs. target-size adaptation. The full method is fine-tuned with RL on instances of the target size, while most baselines are applied zero-shot. To separate generalization from adaptation, please report: (a) zero-shot results, i.e., the supervised model with no RL at the target size, for all source→target pairs, including CVRP and the 10K targets, with the same decoder and beam k-opt; (b) the RL-adapted models evaluated on sizes beyond their RL size, e.g., the 1000-adapted model on 5K and 10K, and the 10K-adapted model on 20K–100K.
  4. Feasibility of the reported CVRP solutions. The node-walk decoder respects capacity by masking (App. B.4), but both later stages use a soft overload penalty. The RL reward is "route cost + ρ·overload after 2-opt" with ρ=3.0 (Table B.3). The CVRP beam k-opt optimizes the penalized objective and "can pass through a briefly overloaded route" (App. B.5). The paper does not state whether final solutions are checked for capacity feasibility, or what happens if a final solution remains overloaded. Please confirm that every reported CVRP solution satisfies all capacity constraints.
4 comments
AuthorsOpenReview ↗

Response to Reviewer ngEG (1/4)

Thank you for the careful review. Your comments helped us clarify how ResizeCO differs from prior RL work, and we added baseline, decoding, and transfer tests.

Critical strengths: We are encouraged that you found ResizeCO to have the lowest gap among learned solvers at comparable runtimes in every main-text setting, with the margin growing at larger sizes. You also highlighted its best learned gap in five of six real-world groups and the innovative presentation of gap–time curves with confidence intervals.

Question 1: Compare with DIMES and CADO using a matched setting.

Following the comment, we compare ResizeCO with DIMES and CADO at TSP sizes 500, 1,000, and 10,000. For a “matched” comparison, we ran DIMES with our GPU beam k-opt search. Note that DIMES uses a stronger decoder (MCTS) and a larger runtime budget than our method. Since CADO has no public code or models, the table below shows the published results with its native 2-opt. ResizeCO uses supervised source sizes 100, 500, and 1,000 for the respective targets. Each table entry is gap (%) / total time (s per instance).

MethodTSP-500TSP-1,000TSP-10,000
ResizeCO0.329 / 0.0200.208 / 0.0462.046 / 2.14
DIMES + beam k-opt1.369 / 27.02.121 / 55.72.629 / 458
CADO (published)0.61 / 0.800.88 / 1.692.68 / 48.8

ResizeCO achieves lower gaps and shorter runtimes than DIMES at all three evaluated TSP sizes, even when DIMES uses our GPU beam k-opt search. ResizeCO gaps and reported times are also better than CADO’s published results. We added these comparisons to the revised paper.

Weakness 1: Training a heatmap with PG and sampling node by node has clear precedent.

We clarify that our key novelty over previous RL methods like DIMES and CADO is not the computation of exact node-walk probabilities itself, but rather their use to enable label-free RL adaptation of a masked-diffusion model pretrained on smaller instances. Our node-walk decoding makes this adaptation possible by providing exact route log-probabilities, and Figure D.3 demonstrates its importance for successful RL training.

DIMES also computes exact node-walk probabilities, but it trains a non-diffusion heatmap with RL at the target size. ResizeCO uses those probabilities to adapt a masked-diffusion model pretrained on small labeled instances. CADO also fine-tunes a diffusion model, but it applies RL to denoising transitions and its reported TSP checkpoints were supervised with target-size labels. ResizeCO instead applies RL to sampled node walks on unlabeled target-size instances. We clarified these differences in the paper.

Question 2: Report A non-diffusion control.

Following this comment we compared ResizeCO (diffusion pretraining on partially-masked solutions) with fully masked heatmap supervision. Both used the same architecture, and runtime budget (60k supervised and 20k RL updates), followed by the same one-step inference configuration (K=C=1). The results were:

MethodCVRP-100 → CVRP-500CVRP-100 → CVRP-1,000
ResizeCO (reduced budget)3.883 / 0.3983.502 / 0.756
Heatmap (matched budget)4.045 / 0.4043.617 / 0.783

ResizeCO slightly outperforms the fully masked heatmap control on both CVRP target sizes under the matched training budget and nearly identical total inference time.

AuthorsOpenReview ↗

Response to Reviewer ngEG (2/4)

Weakness 2: Is ResizeCO a diffusion solver with one unmasking step (K=1) and one correction cycle (C=1)?

With K=C=1, inference uses one heatmap prediction, so the comparison above isolates masked-diffusion pretraining rather than iterative denoising. Training on partially masked solutions also permits multiple unmasking steps and correction cycles, which we test next.

We varied unmasking steps K, parallel samples S, and correction cycles C with the full-budget CVRP-100→CVRP-1,000 model. The preceding reduced-budget control isolates pretraining; this full-budget sweep tests how K, S, and C affect quality as runtime increases. Rows are ordered by runtime; each table entry is gap (%) / total time (s per instance). Bold marks the best gap before slower settings become worse, plus the final minimum.

KSCCVRP-100 → CVRP-1,000
1113.426 / 0.237
1413.202 / 0.306
1813.120 / 0.424
1123.283 / 0.469
2413.147 / 0.489
1423.076 / 0.606
11613.022 / 0.649
1133.178 / 0.677
4413.011 / 0.699
1432.988 / 0.882
13213.010 / 1.115
1153.105 / 1.130
8412.970 / 1.153
1452.923 / 1.473
14812.949 / 1.576
1183.064 / 1.739
16412.878 / 2.080

At similar runtimes, more unmasking steps or correction cycles can outperform extra sampling alone. For example, K=8 with S=4 outperforms K=1 with S=32 at nearly the same time. These gains occur later in the sweep; at short runtimes, which we focus on, increasing S gives the larger gap reduction per unit of time. The main results therefore keep K=C=1. We added this multi-step decoding experiment to the paper and clarified that Figure 1(C) also covers these settings.

AuthorsOpenReview ↗

Response to Reviewer ngEG (3/4)

Question 3: What does target-size RL add over the zero-shot supervised model, and do its gains transfer to larger unseen sizes?

Previous work did zero-shot transfer; label-free adaptation at the target size is our novel contribution. To distinguish the two settings, we report both the gain from target-size RL and transfer of the adapted model beyond its RL size.

First, we compared each supervised checkpoint with the same model after target-size RL, holding the decoder and search fixed. The expanded ablation study we added in the paper reports all 12 TSP/CVRP source-to-target pairs. Each entry below is gap (%) / total time (s per instance).

EvaluationResizeCO (after SL)ResizeCO (after RL)
TSP-100 → TSP-5002.707 / 0.0440.329 / 0.020
TSP-100 → TSP-1,0003.231 / 0.0840.813 / 0.059
TSP-500 → TSP-1,0000.774 / 0.0710.208 / 0.046
TSP-100 → TSP-10,0004.775 / 2.6194.029 / 2.712
TSP-500 → TSP-10,0004.162 / 2.5903.164 / 2.605
TSP-1,000 → TSP-10,0004.073 / 2.7782.046 / 2.144
CVRP-100 → CVRP-5007.445 / 0.2713.176 / 0.109
CVRP-100 → CVRP-1,0006.698 / 0.9013.426 / 0.222
CVRP-500 → CVRP-1,0004.310 / 0.3882.764 / 0.198
CVRP-100 → CVRP-10,0002.531 / 162.011-0.056 / 18.166
CVRP-500 → CVRP-10,0000.703 / 67.724-0.217 / 16.299
CVRP-1,000 → CVRP-10,0000.518 / 60.139-0.096 / 18.047

With the decoder and search held fixed, target-size RL lowers the gap in every source-to-target pair. Measured inference time is also lower in 10 of the 12 pairs.

AuthorsOpenReview ↗

Response to Reviewer ngEG (4/4)

Second, we tested zero-shot transfer beyond the RL size, without further training. The adapted model and its supervised starting point use the same decoder, search, and sample count; bold rows identify their training sizes. Entries are gap (%) / total time (s per instance), with baseline runtimes shown for context.

EvaluationResizeCO (after SL)ResizeCO (after RL)SIT
Supervised training: TSP-500, RL adaptation: TSP-1,000
TSP-2,000 (S=8)2.153 / 3.3900.482 / 1.0581.967 / 1.348
TSP-5,000 (S=8)3.437 / 7.6483.133 / 8.4612.542 / 8.364
TSP-10,000 (S=1)4.174 / 2.6764.198 / 2.8273.629 / 3.855
Supervised training: TSP-1,000, RL adaptation: TSP-10,000
TSP-20,000 (S=1)4.985 / 9.633.908 / 8.325.151 / 7.33
TSP-50,000 (S=1)10.867 / 54.0310.140 / 54.045.853 / 64.25
EvaluationResizeCO (after SL)ResizeCO (after RL)MaskCO
Supervised training: CVRP-500, RL adaptation: CVRP-1,000
CVRP-5,000 (S=1)1.525 / 12.2490.926 / 5.9042.985 / 6.95
CVRP-10,000 (S=1)0.703 / 67.7240.317 / 31.6787.971 / 29.34
Supervised training: CVRP-1,000, RL adaptation: CVRP-10,000
CVRP-20,000 (S=1)-0.016 / 131.7-0.610 / 38.5381.481 / 78.11
CVRP-50,000 (S=1)2.019 / 691.7-0.864 / 498.3863.302 / 194.5 (13/16 feasible solutions)

Without further training at the larger evaluation sizes, adaptation improves on its supervised starting point in every CVRP row and four of five TSP rows. It achieves the lowest gap in every CVRP row and two TSP rows. At one TSP size, its gap is slightly higher than the supervised model’s. These results show a clear zero-shot transfer benefit in addition to our main label-free target-size adaptation claim. At 100,000 nodes, dense pairwise tensors exceed available memory; extending the method there needs a more memory-efficient architecture. We added these evaluations to the paper and distinguished adaptation from transfer beyond the RL size.

Question 4: Are the final CVRP solutions feasible?

Yes. We checked every reported ResizeCO CVRP output, including CVRPLIB, and observed 100% capacity feasibility. No infeasible output was excluded.

The decoder enforces capacity during construction, but local search can temporarily overload routes because it uses a soft penalty. Moving one customer to reduce overload saves at least ρ=3\rho=3 in penalty. Its distance cost is at most 222\sqrt{2}: removing it cannot lengthen the old route, and inserting it adds at most two edges of length 2\sqrt{2} (all reported CVRP search coordinates are in [0,1]2[0,1]^2). Thus any available such move lowers the penalized search cost.

The penalty favors repair, but it cannot guarantee a feasible final route. Our 100% feasibility claim therefore comes from checking every reported final output, including CVRPLIB. Gaps use the unpenalized lengths of these feasible routes; a negative gap means ResizeCO found a shorter route than the HGS reference. We added this explanation and the observed feasibility rates to the paper.

Comments on the paper

3 comments
AuthorsOpenReview ↗

Response to Reviewer 4EkP (1/3)

Thank you for the careful review. Your questions helped us clarify CVRP search and decoding, and we ran matched RL and broader-capacity tests.

Critical strengths: Your review highlights ResizeCO’s large-scale results: it achieves a lower TSP-10,000 gap than SIT in less time and feasible CVRP-10,000 routes with lower average cost than the HGS references. You also recognize two contributors to the full solver: GPU beam k-opt for refinement and RL, whose benefit the fixed-search TSP ablation isolates.

Weakness 1 / Question 1: Does RL help under matched search and runtime?

On CVRP-10,000, we compared ResizeCO after SL and after RL with identical decoding and refinement settings. We also applied 2-opt and GPU beam k-opt to nearest-neighbour and MaskCO constructions. Each control had the same total inference-time budget as ResizeCO after RL, including construction and refinement.

MaskCO uses its released size-500 model with K=4 and C=1. We shortened its native 2-opt stage to leave time for our search within the same total allowance. The final column is gap (%) / total time (s per instance).

MethodRaw gap (%)2-opt gap (%)Final gap / time
ResizeCO (after RL)3.1701.785-0.089 / 18.36
ResizeCO (after SL)34.38410.7433.096 / 18.38
Nearest neighbour3.2891.8490.191 / 15.52
MaskCO526.086457.769348.958 / 18.38

ResizeCO after RL improves both raw and final gaps over ResizeCO after SL with the same refinement stages. Nearest neighbour starts with a similar raw gap, but falls further behind after search. Because RL rewards routes after 2-opt, we expect its advantage to be most visible after refinement.

The next table breaks down per-instance construction, 2-opt, and beam time for ResizeCO after RL, ResizeCO after SL, and nearest neighbour. It also reports mean and maximum beam-search sweeps.

MethodBuild (s)2-opt (s)Beam (s)Mean sweepsMax sweeps
ResizeCO (after RL)2.0152.02414.194345.9432
ResizeCO (after SL)2.0022.00714.248345.2432
Nearest neighbour0.3332.06213.001320.5403

ResizeCO after RL and after SL have nearly the same stage times and sweep counts, so extra search time does not explain their gap difference shown above. We extended the component ablations to all 12 TSP/CVRP source-to-target pairs in the appendix.

AuthorsOpenReview ↗

Response to Reviewer 4EkP (2/3)

Weakness 2 / Question 4: Does CVRP transfer extend beyond Q=50?

Here Q is vehicle capacity: a higher Q lets each route carry more demand and can increase the number of customers served per route. We removed the 7–14 customers-per-sub-route filter and evaluated every instance in the two smaller CVRPLIB bands. The 7,000–15,000-customer band was already unfiltered; its 21–100 customers per sub-route are observed, not selected. Both tables report gap (%) / total time (s per instance).

MethodCVRPLIB 321–684 n=36CVRPLIB 748–956 n=12
ResizeCO4.223 / 0.4514.592 / 0.763
MaskCO4.781 / 0.5005.548 / 0.548
ReLD4.062 / 0.5604.795 / 0.990

Without the filter, ResizeCO still beats MaskCO in both smaller CVRPLIB bands. It has the lowest gap in the 748–956 band and runs faster than ReLD in both; ReLD has a slightly lower gap in the 321–684 band. These unfiltered results strengthen the real-world evidence, and we made their scope explicit in the paper.

We also tested Q=250 and Q=1,000 on SIT’s larger-capacity distributions, outside the main synthetic Q=50 setting. At Q=250, we adapted the size-1,000 supervised model with label-free GRPO on this distribution. At Q=1,000, we started from a model fine-tuned with labels at Q=100, ran the beam search inside the reward, and used a longer search at test time. SIT uses PRC20 at Q=250 and PRC100 at Q=1,000. ReLD uses augmentation ×8 at Q=250 but no augmentation at Q=1,000 because ×8 exceeds GPU memory.

MethodCVRP-1,000 Q=250CVRP-10,000 Q=1,000
ResizeCO3.695 / 0.8863.142 / 80.075
SIT3.998 / 1.1490.477 / 62.270
ReLD9.166 / 0.59519.216 / 15.683

At Q=250, ResizeCO beats SIT in both gap and runtime and has the lowest gap overall. At Q=1,000, SIT leads, but ResizeCO has a substantially lower gap than ReLD, with a longer runtime. These results establish strong performance beyond Q=50 while showing where SIT leads.

AuthorsOpenReview ↗

Response to Reviewer 4EkP (3/3)

Question 2: How does CVRP beam search handle move conflicts and route loads?

In your 49/50 example, the deployed search produced no overload and served every customer once. The two insertions touch the same sub-route, so the conflict check selects at most one per sweep. More generally, we combine moves only across different sub-routes. We recompute each candidate’s length and overload penalty before acceptance and update loads before the next sweep.

Across the reported CVRP evaluations, including CVRPLIB, we observed 100% final feasibility. No infeasible output was excluded.

The conflict check prevents incompatible moves, but an individual move can still create overload. The penalty then favors repair: moving one customer to reduce overload saves at least ρ=3\rho=3, because demands are integers. Removing that customer cannot lengthen its old route, and inserting it adds at most two edges of length 2\sqrt{2} on the unit square. The distance cost is therefore at most 22<32\sqrt{2} < 3, so any available such move lowers the penalized search cost.

This repair incentive is not a feasibility guarantee: no hard constraint or final repair step rules out an infeasible termination. We therefore report the observed 100% rate from direct checks of final outputs. Costs are unpenalized feasible route lengths; a negative gap means a feasible solution is shorter than the HGS reference. We clarified the sub-route conflict check in Appendix B.5 and added the feasibility rates to the paper.

Question 3: When can the CVRP decoder return to the depot, and how is the walk likelihood computed?

The decoder can return while feasible customers remain; the return is forced only when none fits. Each walk begins at the depot, then takes a first customer sampled uniformly without replacement across the S walks.

The first customer is sampled independently of model parameters, so the walk likelihood is conditional on it. Every later sampled decision, including a voluntary depot return, adds its log-probability; a forced return adds zero because it is the only available action. The pseudocode makes this explicit.

Require: G instance with depot n₀, customers V and demands q, Q capacity, pθ heatmap, S routes
 1: for s = 1 … S do                                                ▷ distinct start nodes
 2:     n₁ ← the s-th start node, U₁ ← V \ {n₁}, load ← q(n₁), log pθ(routeₛ) ← 0, j ← 1
 3:     while Uⱼ ≠ ∅ do
 4:         Aⱼ ← {n ∈ Uⱼ : load + q(n) ≤ Q}, plus n₀ if nⱼ ≠ n₀     ▷ feasible next nodes
 5:         draw nⱼ₊₁ ~ πθ(· | sⱼ ; pθ) with Aⱼ in place of Uⱼ      ▷ Eq. (2)
 6:         log pθ(routeₛ) ← log pθ(routeₛ) + log πθ(aⱼ | sⱼ ; pθ)  ▷ zero if Aⱼ = {n₀}
 7:         load ← 0 if nⱼ₊₁ = n₀, else load + q(nⱼ₊₁), Uⱼ₊₁ ← Uⱼ \ {nⱼ₊₁}, j ← j + 1
 8:     end while
 9:     routeₛ ← (n₀, n₁, …, nⱼ, n₀)
10: end for

The walk likelihood sums only the decoder’s sampled choices; the final forced depot return adds zero. Search changes the route used to compute the reward, but not the likelihood of the sampled walk. We added this pseudocode to the paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.