acceptodds
Under review as a conference paper at ICLR 2027

Imperfect Is Perfect: Learned Column Prefilling for Branch-Price-and-Cut

Abstract

Column generation folklore warns that initial columns hurt: a warm start may bias the dual and slows the root of branch-price-and-cut. We show the opposite once the columns are *imperfect in the right way*. Preloading the support of the optimal root LP, the best columns one could know in advance, fails to finish on half of our hardest instances; a pool of ordinary routes that need not belong to any optimal solution, held outside the master and priced at the current smoothed dual, speeds the root up. Because the columns need not be optimal, producing them becomes a learning task: a neural edge scorer guides a constructive generator that builds the pool in seconds. A second network predicts the initial center of Wentges smoothing from the instance file, and with it the direction of the smoothed pricing queries; the solver's own updates run unchanged. With prefill and center in place, exact pricing dominates root pricing time, so we rebuild bucket-graph labeling around its dominance test for the GPU and certify on the CPU. Inside RouteOpt, the state-of-the-art exact solver for capacitated vehicle routing, the pipeline reaches the same certified root bound in **13.2%** of vanilla RouteOpt's root pricing time over 95 instances with 300 to 1000 customers, prefill alone in **26.1%**, and **17.5×** faster in the best case. In an exact branch-price-and-cut solver for unrelated parallel machine scheduling, prefill with smoothing and the learned center certifies **all 25** benchmark instances, **12×** faster than the solver's own column generation, which certifies 20 of them.

Primary area:
optimization
Keywords:
column generation, branch-price-and-cut, dual stabilization, learning to optimize

Reviews

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

The authors propose an approach to accelerate branch-price-and-cut. Their main claim is that, unlike what the folklore warns, using initial columns might not be harmful when the initial pool consists of imperfect columns that are used to steer the column generation trajectory. Their proposed method consists of 3 parts: A learned prefill to score and construct routes. A learned dual center (using a Set Transformer) to predict the initial center of dual smoothing. And a GPU exact pricing that accelerates computation while ensuring exactness. They tested on 95 CVRP instances of 300-1000 customers and 25 instances of parallel-machine scheduling, comparing against RouteOpt. They show a 7.6x geometric-mean speedup in CVRP and a 12x speedup on parallel-machine scheduling.

Critical strengths
  1. The observation that imperfect columns help more than optimal ones is an interesting and innovative idea.
  2. The results are impressive: 7.6x and 12x speedups on 2 problem classes and an ablation study to show where improvements come from. Their suggested method not only improves runtimes but also doesn't sacrifice exactness, making the approach more convincing than just basing correctness on learned predictions.
Critical weaknesses
  1. There isn't a full-tree evaluation, it isn't clear how the speedup translates to solving the complete instance.
  2. The authors use the scheduling experiment as evidence for generality, but they use randomized list scheduling instead of the scorer. Making their claim of generality and robustness to other problems and distributions less impactful.
Questions for authors
  1. Do you have results on the total solve time or search-tree size for the complete branch-and-price-and-cut solver? Even in small-scale instances?
  2. Have you evaluated zero-shot generalization on CVRP instances from different distributions or size ranges, without retraining?
5 comments

Response to Reviewer GX6M (Part 1/3)

We thank the reviewer for the positive assessment and for the two concrete questions, which we answer below.

W1 and Q1: Full-tree evaluation

Root-level evaluation in the literature. In the literature on dual stabilization, essentially all proposed methods are compared at the root only, including the key publications in prestigious journals: Ben Amor, Desrosiers and Valério de Carvalho (2006, Operations Research), Clautiaux et al. (2011, INFORMS Journal on Computing), Gschwind and Irnich (2016, IJOC), Pessoa et al. (2018, IJOC), Costa et al. (2022, IJOC) and Guo, Xiao and Liang (2025, Operations Research) all report the time or the number of iterations needed to solve the root linear relaxation, and none of them compares branch-and-price trees. Gschwind and Irnich clearly state that "The results presented in this paper all refer to the solution of the linear relaxation of the extensive formulation."

Because dual stabilization is regarded as a general-purpose technique, the acceleration expected from it is also moderate. Pessoa et al. (2018) report that automatic Wentges smoothing reduces the master-LP time by 35% on CVRP and by 41% on bin packing and on shift scheduling, and gives no gain on cutting stock or vertex coloring (speedup factors 0.98 and 1.01); for cutting stock, Gschwind and Irnich (2016) find that static dual inequalities give "an average speedup of about one-third" and that the additional dynamic ones save "an extra 17% of the computation time". Moreover, on a more state-of-the-art solver this effect may be discounted further, because of its complementarity with the solver's other components.

Learning inside exact solvers. Most work on learning inside exact solvers likewise stays at the root, in part because the problems met deeper in the tree, after branching decisions and added cuts, shift away from the distribution the models are trained on. Examples are our scheduling baseline, the learned pricer of Hijazi, Özaltın and Uzsoy (2026, IJOC), which is evaluated by column generation run to convergence, and NeuralSEP (Kim, Park and Kwon, 2024, IJOC), which compares learned separation "within the cutting plane method to solve the relaxed LP problem at the root node" and leaves its incorporation into state-of-the-art branch-price-and-cut to future research. The learned column and arc selection of Morabit, Desaulniers and Lodi (2021, Transportation Science; 2023, INFORMS Journal on Optimization) and the learned dual prediction of Kraul, Seizinger and Brunner (2023, IJOC) are evaluated at the root as well.

Why our approach can carry over to the tree. Our method nevertheless contains an idea that transfers well to the full tree, which we will develop in the future-work discussion on the full tree: it compresses the share of heuristic pricing while providing a system-level solution for efficient exact pricing. Table D2 in our response to Reviewer bAGu shows this compression at the root: the share of root time spent in heuristic pricing falls from 85 % to 39 % with Prefill + Center. This combination is what can keep the effect on the full tree.

Response to Reviewer GX6M (Part 2/3)

Full-tree results. We ran all 22 Vrp-Set-X instances with 100 to 200 customers with the complete RouteOpt branch-price-and-cut (cutting and branching enabled), under two setups: UB = opt, where the known optimum is given as the initial upper bound and the tree only has to prove it, and UB = BKS + 1, where the tree also has to find the optimum. Under both setups, 21 of them are solved to proven optimality within six hours; X-n190-k8 is not solved by any configuration, vanilla included, and is therefore excluded from Table A1. Table A1 gives, per instance and setup, the whole-tree wall-clock time in seconds and, in parentheses, the number of nodes for vanilla RouteOpt and for our full pipeline.

Table A1. Whole-tree time in seconds (nodes) and per-instance ratio; the last row gives the geometric mean and, in parentheses, the number of instances faster than vanilla.

UB = optUB = BKS + 1
InstanceVanillaFull pipelineFull / vanillaVanillaFull pipelineFull / vanilla
X-n101-k252.0 (1)1.0 (1)0.492.3 (1)1.0 (1)0.43
X-n106-k1425 (1)11 (1)0.4226 (1)12 (1)0.47
X-n110-k134.7 (1)2.8 (1)0.605.0 (1)2.8 (1)0.57
X-n115-k1029 (1)19 (1)0.6531 (1)25 (1)0.81
X-n120-k6793 (7)448 (5)0.561 057 (9)488 (7)0.46
X-n125-k3049 (3)66 (3)1.3651 (3)46 (3)0.90
X-n129-k1885 (3)58 (3)0.6857 (3)59 (3)1.04
X-n134-k131 752 (19)2 207 (33)1.262 157 (31)1 578 (19)0.73
X-n139-k10115 (1)173 (1)1.50110 (1)182 (1)1.66
X-n143-k76 170 (53)3 240 (33)0.536 161 (53)2 858 (27)0.46
X-n148-k463.3 (1)2.6 (1)0.795.6 (1)3.1 (1)0.55
X-n153-k22446 (13)340 (19)0.76436 (13)260 (13)0.60
X-n157-k1319 (1)14 (1)0.7524 (1)16 (1)0.68
X-n162-k11946 (5)558 (3)0.591 549 (5)608 (3)0.39
X-n167-k10424 (1)217 (1)0.51370 (1)195 (1)0.53
X-n172-k51110 (3)60 (3)0.5487 (5)79 (3)0.91
X-n176-k26126 (7)82 (9)0.65117 (5)91 (9)0.78
X-n181-k23131 (9)101 (9)0.78160 (11)152 (15)0.95
X-n186-k158 478 (97)4 296 (69)0.519 760 (95)3 285 (61)0.34
X-n195-k5160 (5)43 (7)0.7267 (7)51 (5)0.77
X-n200-k36586 (59)498 (47)0.85693 (91)599 (57)0.86
Geometric mean0.695 (18/21)0.659 (19/21)

Reading the table. First, with a state-of-the-art exact solver most instances with 100 to 200 customers close within 3 to 5 nodes: vanilla RouteOpt closes 13 of the 22 instances within five nodes, 8 of them at the root node itself, so the root is indeed the dominant part. For the instances with larger trees there is considerable uncertainty tied to the search trajectory, and the comparison should be read together with the tree size: on X-n134-k13 under UB = opt the full pipeline explores 33 nodes against 19 for vanilla.

These results show that our current pipeline has room to go further into the full tree. As for NeuralSEP and the learned scheduling pricer, the distributions met later in the tree require their own training before better results can be expected there.

W2 and Q2: Generality

Why parallel-machine scheduling, and why no scorer there. We chose parallel-machine scheduling because it is the problem of the most recent learning-to-generate-columns baseline, Hijazi, Özaltın and Uzsoy (2026, IJOC). This problem is much simpler than the VRP: its pricing problem is in essence a search for a subset rather than for a sequence, since for a fixed job set the weighted-shortest-processing-time order is optimal on each machine (Appendix A.5). In this case a randomized subset, as produced by randomized list scheduling, already meets the coverage and diversity we require of the pool, and a sequence generator such as our learned scorer is no longer needed.

Problems with VRP-like pricing. Problems whose pricing is as complex as in the VRP each have their own dedicated exact solver and problem-specific heuristics, so porting the pipeline to each of them is a large amount of work; we believe that domain experts in those problems can transfer the approach well.

Response to Reviewer GX6M (Part 3/3)

Zero-shot generalization within CVRP. In addition, to show generality, we evaluated the pipeline on CVRP instances from other generation distributions, zero-shot, without any retraining. We used four families from the generator of Zhou et al. (2023): uniform (U), clustered (C), mixed (M) and explosion (E), five instances each at n = 300 and n = 500, with demands 1 to 9. The same coordinates and demands are solved at three capacities, Q = 25, 50 and 200, which move the average route size to about 5, 10 and 40 customers (the very-short, medium and ultra-long classes); 120 instances in all. Pool and center come from the frozen models, and every configuration reaches the same certified root bound. Table A2 gives the root-time ratio to vanilla RouteOpt (geometric mean; in parentheses, the number of instances faster than vanilla).

Table A2. Zero-shot root pricing on the distributions of Zhou et al. (2023).

GroupInst.Q = 25: Prefill+CenterQ = 25: Full pipelineQ = 50: Prefill+CenterQ = 50: Full pipelineQ = 200: Prefill+CenterQ = 200: Full pipeline
U100.117 (10/10)0.096 (10/10)0.137 (10/10)0.089 (10/10)0.219 (10/10)0.147 (10/10)
C100.112 (10/10)0.097 (10/10)0.137 (10/10)0.089 (10/10)0.243 (10/10)0.146 (10/10)
M100.115 (10/10)0.101 (10/10)0.155 (10/10)0.106 (10/10)0.200 (10/10)0.117 (10/10)
E100.102 (10/10)0.086 (10/10)0.148 (10/10)0.099 (10/10)0.207 (10/10)0.129 (10/10)
n = 300200.115 (20/20)0.111 (20/20)0.165 (20/20)0.117 (20/20)0.239 (20/20)0.154 (20/20)
n = 500200.107 (20/20)0.081 (20/20)0.126 (20/20)0.078 (20/20)0.197 (20/20)0.117 (20/20)
all400.111 (40/40)0.095 (40/40)0.144 (40/40)0.096 (40/40)0.217 (40/40)0.134 (40/40)

Vanilla median root time: 11 s / 55 s (Q = 25, n = 300 / 500), 29 s / 132 s (Q = 50), 350 s / 1 550 s (Q = 200).

On every family and at every capacity both configurations are faster than vanilla on all instances, and the full pipeline brings root pricing to 0.095, 0.096 and 0.134 of vanilla's time: the pipeline is robust and strong across these distributions.

References

  • H. Ben Amor, J. Desrosiers, J. M. Valério de Carvalho. Dual-optimal inequalities for stabilized column generation. Operations Research 54(3):454–463, 2006.
  • F. Clautiaux, C. Alves, J. Valério de Carvalho, J. Rietz. New stabilization procedures for the cutting stock problem. INFORMS Journal on Computing 23(4):530–545, 2011.
  • L. Costa, C. Contardo, G. Desaulniers, J. Yarkony. Stabilized column generation via the dynamic separation of aggregated rows. INFORMS Journal on Computing 34(2), 2022.
  • T. Gschwind, S. Irnich. Dual inequalities for stabilized column generation revisited. INFORMS Journal on Computing 28(1):175–194, 2016.
  • S. Guo, F. Xiao, Z. Liang. Nested set-covering/packing problem: degeneracy alleviation and dual stabilization. Operations Research 73(6), 2025.
  • A. Hijazi, O. Y. Özaltın, R. Uzsoy. An improving column is all you need: enhancing column generation for parallel machine scheduling via transformers. INFORMS Journal on Computing, 2026.
  • H. Kim, J. Park, C. Kwon. A neural separation algorithm for the rounded capacity inequalities. INFORMS Journal on Computing 36(4):987–1005, 2024.
  • S. Kraul, M. Seizinger, J. O. Brunner. Machine learning–supported prediction of dual variables for the cutting stock problem with an application in stabilized column generation. INFORMS Journal on Computing 35(3), 2023.
  • M. Morabit, G. Desaulniers, A. Lodi. Machine-learning–based column selection for column generation. Transportation Science 55(4), 2021.
  • M. Morabit, G. Desaulniers, A. Lodi. Machine-learning–based arc selection for constrained shortest path problems in column generation. INFORMS Journal on Optimization, 2023.
  • A. Pessoa, R. Sadykov, E. Uchoa, F. Vanderbeck. Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS Journal on Computing 30(2):339–360, 2018.
  • J. Zhou, Y. Wu, W. Song, Z. Cao, J. Zhang. Towards omni-generalizable neural methods for vehicle routing problems. ICML, 2023.
Reviewer_8oVYOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2(+1)
Read review
Paper summary

This paper proposes a learning-enhanced pipeline to accelerate root column generation in branch-price-and-cut. A neural edge scorer guides a constructive generator to build a diverse pool of feasible routes. A second model predicts the initial center of Wentges smoothing to guide the dual trajectory, while a GPU implementation accelerates exact bucket-graph pricing with final CPU certification. Integrated into RouteOpt, the full pipeline achieves a 7.6-fold speedup while reaching the same LP bound.

Critical strengths

The idea of learning to prefill is novel and well-motivated.

Critical weaknesses
  1. The writing of many paragraphs, even the abstract, is not natural.

  2. The speedup seems to come from simpler engineering tricks, rather than the machine learning part. As shown in the experiment section, a route pool built by a standard heuristic, with no neural network, gets almost the same speedup as the learned one (0.377 vs. 0.305, in Table 11). And when we exclude the learned dual center, most of its benefit remains (0.719 vs. 0.611, in Table 12).

  3. Most experiments in this paper are about root pricing, not the full solving process. In the solver of CVRP, empirical gains from the first root-solving stage may not survive to final solutions.

Questions for authors

N/A

5 comments

Response to Reviewer 8oVY (Part 1/2)

We thank the reviewer for reading our paper and for finding the idea of learning to prefill novel and well motivated.

W1: Writing

We used generative AI tools to help draft parts of some sections within a framework we had written ourselves, as disclosed in the AI use statement of the paper. The final manuscript went through several rounds of reading and revision by the authors, and we confirm that it expresses our own ideas in our own words.

The paper studies dual stabilization and pricing acceleration inside a modern state-of-the-art exact branch-price-and-cut (BPC) solver, and each of its components rests on intricate implementation details. Given the page limit, the main text concentrates on the key steps that carry our ideas, and the appendix supplies the complete background: branch-price-and-cut and column generation in Appendix A, the learning components in Appendix B, and the GPU exact pricer in Appendix C. We will polish the writing.

W2: "Simpler engineering tricks"

Perhaps precisely because the paper builds the pipeline up step by step, the idea may look so obvious that it reads as an engineering trick. In fact, as the column-generation folklore warns, initial columns are not always beneficial.

On the one hand, the optimal basis does not help: in a preliminary experiment on ultra-long XML instances, preloading the converged basis made the root 1.22 times slower on average over 16 instances, with 10 of them slower and per-instance ratios ranging from 0.83 to 4.56.

On the other hand, the X set of Table 11 is comparatively benign: its route lengths are moderate, and it has no ultra-long route class. On harder instances, a heuristic pool had a significant side effect in our development: a plateau. The dual gets stuck on a plateau. Pricing still returns columns, but the dual objective does not improve, and columns pile up in the master. Table B1 shows this on the fifteen ultra-long instances of our panel (XML300, XML400 and XML500).

Table B1. Root time in seconds on the fifteen ultra-long XML instances.

InstanceAll components offHGS-filledPrefillPrefill + Center
XML300_1136_01124956246
XML300_1166_019931 060284246
XML300_1346_01369411167154
XML300_2176_015941 158334140
XML300_2366_012 0874 951570486
XML400_1136_01638786289212
XML400_1226_01686659283229
XML400_1346_01719748273244
XML400_2366_01554741216160
XML400_3356_01480392241224
XML500_1126_011 7872 762970621
XML500_1176_011 7762 280596361
XML500_1276_012 8253 0441 3461 059
XML500_1346_014 4879 8221 7301 216
XML500_3266_015 4764 0051 8271 750
Geometric mean of the ratio to all components off (faster/finished)11.218 (4/15)0.410 (15/15)0.311 (15/15)

Moreover, HGS is itself the heuristic that our analysis of coverage and diversity points to (Section 3.1): what shortens the root is coverage, many distinct customer sets with each customer in many of them, and a seed-based population heuristic produces exactly such coverage, with HGS the strongest known metaheuristic for the CVRP. In fact, there are several strong heuristics that are not seed-based, such as SISR (Christiaens and Vanden Berghe, 2020), LKH-3 (Helsgaun, 2017) and the GPU solver NVIDIA cuOpt. We therefore also built pools with these three heuristics on the hard instances.

Table B2. Root time in seconds, with each column named by its initialization source. Generation time is not included: at most 60 s for cuOpt, LKH-3 and HGS, 300 s for SISR, and less than 0.25 s for the learned prefill. * marks a run over the 12 h time limit.

InstanceAll components offcuOptLKH-3SISRHGSLearned prefill
XML400_1136_016388199894 509786289
XML400_1226_016866575521 407659283
XML400_1346_017196044483 154748273
XML400_2366_015541 1866457 311741216
XML400_3356_01480452387510392241
XML500_1126_011 7874 5342 45530 1302 762970
XML500_1176_011 7762 4553 61921 3842 280596
XML500_1276_012 8257 8314 959> 43 200 *3 0441 346
XML500_1346_014 4877 5125 721> 43 200 *9 8221 730
XML500_3266_015 4767 8124 2948 9424 0051 827
Geometric mean of the ratio to all components off (faster/finished)11.474 (3/10)1.136 (4/10)4.828 (0/8), 2 capped1.165 (3/10)0.416 (10/10)

Response to Reviewer 8oVY (Part 2/2)

Regarding Table 12, we believe there is a misunderstanding: the Crand arm does not exclude the learned dual center. Crand takes the deployed learned center and randomly permutes its customer entries, keeping its magnitude, its vehicle dual and the box projection; it destroys the learned direction and nothing else (Appendix D.2). The arm without a learned center is S, standard Wentges smoothing, at 0.837 of vanilla, against 0.611 with the learned center, which is 1.37 times faster.

W3: Full tree

Evaluating the root only is the common metric in nearly all related work on dual stabilization and on learning for column generation. However, we believe our idea of reducing the share of heuristic pricing carries over to the full tree. Without any further training, we report full-tree results on the X instances with 100 to 200 customers, under two incumbent settings, in our response to Reviewer GX6M (W1 and Q1).

References

  • Christiaens, J. and Vanden Berghe, G. (2020). Slack induction by string removals for vehicle routing problems. Transportation Science, 54(2), 417–433.
  • Helsgaun, K. (2017). An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems. Technical report, Roskilde University.
  • NVIDIA cuOpt. GPU-accelerated optimization engine for routing problems. https://github.com/NVIDIA/cuopt.
  • Vidal, T. (2022). Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Computers & Operations Research, 140, 105643.

Dear Reviewer 8oVY,

Thank you again for your time in reviewing our paper. As the discussion period ends on November 18 (AoE), we would like to kindly check whether our response has addressed your concerns, in particular on the role of learning (W2) and on the full tree (W3). If any question remains, we would be glad to clarify it while the discussion window is still open. If our response has resolved your concerns, we would be grateful if you would consider updating your assessment.

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

In this paper, the authors propose three components to accelerate column generation in RouteOpt: 1) a learning-based column prefilling framework, 2) a learned dual-center initialization method, and 3) a GPU-based exact pricing implementation. These components aim to reduce the computational cost of column generation while preserving exactness.

Experimental results demonstrate substantial reductions in root-pricing time compared with the original RouteOpt, achieving a geometric mean speedup of approximately 7.6× on 95 CVRP instances.

Critical strengths

I have a positive impression of this work.

The paper presents a meaningful improvement to RouteOpt, one of the strongest exact solvers for CVRP, to the best of my knowledge. The reductions in root-pricing time are quite impressive.

Another important strength is the clear motivation behind the proposed method. The three components are well motivated and supported by thorough analyses. The authors provide useful insights into how these components interact with a well-established exact solver.

Critical weaknesses

However, I have several concerns, as detailed below.

Major Concerns

  1. Lack of end-to-end BPC evaluation.

The authors do not report the end-to-end BPC runtime, but only compare root-pricing times. Although this is a reasonable choice for large-scale instances, the authors should also investigate the complete BPC runtime (as well as other relevant metrics) on smaller instances for which optimality can be certified within a reasonable time.

In the Limitations section, the authors state: “at the scale we test, the instances have no known exact solution time, and root pricing is the part we can measure and certify; extending the measurement to the tree is one direction of future work.”

However, a more detailed end-to-end analysis should be feasible for instances such as X-n101-k25 and X-n200-k36.

  1. Generalization beyond X-like instances.

The authors should further investigate generalization beyond X-like instances. The main results in Table 1 focus on XML and Set-X instances. Although these benchmarks are widely accepted in the CVRP community, the XML generator is closely related to the generator originally used to construct Set-X. Therefore, the reported results do not fully demonstrate the transferability of the learned components. (Training time counts.)

I encourage the authors to consider additional distributions, such as instances with uniformly distributed demands and locations in [1] or specially designed distributions in [2].

  1. Transparency of instance selection.

The authors evaluate only a selected subset of instances, but the selection procedure is not sufficiently transparent. It would be helpful to provide the complete list of selected instances and clarify the selection criteria.

While evaluating the complete benchmark may require additional computation, I encourage the authors to extend the evaluation where feasible or at least justify the current selection.

Minor Concerns

  1. Additional training information.

The authors provide useful information about the model architectures and training settings. However, additional training information would improve transparency and help readers better understand the learning process.

In particular, it would be helpful if the authors reported the training time, computational resources, and training and validation losses. It would also be useful to report the validation metrics (and analysis) used for checkpoint selection.

  1. Comparison with multi-threaded CPU exact pricing.

It would be helpful if the authors could compare the proposed GPU exact-pricing implementation with a multi-threaded CPU exact-pricing implementation and explain the factors contributing to the observed GPU performance.

References

[1] Berto, F., Hua, C., Zepeda, N. G., et al. RouteFinder: Towards Foundation Models for Vehicle Routing Problems. Transactions on Machine Learning Research, 2025. https://openreview.net/forum?id=QzGLoaOPiY

[2] Zhou, J., Wu, Y., Song, W., et al. Towards Omni-Generalizable Neural Methods for Vehicle Routing Problems. Proceedings of the 40th International Conference on Machine Learning, 2023.

Questions for authors

see weaknesses

5 comments

Response to Reviewer bqGb (Part 1/3)

We sincerely thank the reviewer for the positive assessment and for the constructive and detailed suggestions. Each of them points to an analysis that makes the paper stronger, and we have carried them out below.

Major 1: End-to-end BPC evaluation

Root pricing is the comparison benchmark in nearly all work on dual stabilization and on learning for column generation; we discuss this literature in detail in our response to Reviewer GX6M (W1 and Q1). Our idea of reducing the share of heuristic pricing, however, has the potential to go beyond this benchmark. We therefore also compared complete branch-price-and-cut runs on the Vrp-Set-X instances with 100 to 200 customers, including X-n101-k25 and X-n200-k36, under two incumbent settings. The per-instance runtimes and node counts are in Table A1 of our response to Reviewer GX6M.

Major 2: Generalization beyond X-like instances

The strongest point of XML is that it directly controls route size, the property that matters most for the difficulty of branch-price-and-cut, and therefore lets one construct instances of every kind. We believe that our results carry over to any CVRP instance. To support this claim, we built a set of instances on the instance families of [2] (Zhou et al., 2023), again focusing on instance size and route size. We used four families: uniform (U), clustered (C), mixed (M) and explosion (E), five instances each at n = 300 and n = 500, with demands 1 to 9; the uniform family also covers the uniform setting of [1]. The same coordinates and demands are solved at three capacities, Q = 25, 50 and 200, which move the average route size to about 5, 10 and 40 customers (the very-short, medium and ultra-long classes of the paper); 120 instances in all. The test is zero-shot: pool and center come from the frozen models, and nothing was retrained. All configurations of an instance run in the same job on the same node and reach the same certified root bound. For all of Tables C1 to C3, each cell gives the geometric-mean root-time ratio to vanilla RouteOpt and, in parentheses, the number of instances faster than vanilla.

Table C1. Q = 25, very short routes. Vanilla median root time: 11 s (n = 300) and 55 s (n = 500).

GroupInst.PrefillCenterPrefill + Center
U100.097 (10/10)0.658 (10/10)0.117 (10/10)
C100.094 (10/10)0.707 (10/10)0.112 (10/10)
M100.093 (10/10)0.690 (10/10)0.115 (10/10)
E100.085 (10/10)0.709 (9/10)0.102 (10/10)
n = 300200.099 (20/20)0.556 (19/20)0.115 (20/20)
n = 500200.085 (20/20)0.858 (20/20)0.107 (20/20)
all400.092 (40/40)0.691 (39/40)0.111 (40/40)

Table C2. Q = 50, medium routes. Vanilla median root time: 29 s (n = 300) and 132 s (n = 500).

GroupInst.PrefillCenterPrefill + Center
U100.138 (10/10)0.545 (10/10)0.137 (10/10)
C100.126 (10/10)0.582 (10/10)0.137 (10/10)
M100.148 (10/10)0.654 (10/10)0.155 (10/10)
E100.140 (10/10)0.620 (10/10)0.148 (10/10)
n = 300200.150 (20/20)0.528 (20/20)0.165 (20/20)
n = 500200.127 (20/20)0.679 (20/20)0.126 (20/20)
all400.138 (40/40)0.599 (40/40)0.144 (40/40)

Table C3. Q = 200, ultra-long routes. Vanilla median root time: 350 s (n = 300) and 1 550 s (n = 500).

GroupInst.PrefillCenterPrefill + Center
U100.372 (10/10)0.306 (10/10)0.219 (10/10)
C100.262 (10/10)0.352 (10/10)0.243 (10/10)
M100.282 (10/10)0.319 (10/10)0.200 (10/10)
E100.329 (10/10)0.300 (10/10)0.207 (10/10)
n = 300200.364 (20/20)0.322 (20/20)0.239 (20/20)
n = 500200.262 (20/20)0.315 (20/20)0.197 (20/20)
all400.308 (40/40)0.319 (40/40)0.217 (40/40)

These results agree with our claims and with what we observe on XML and Vrp-Set-X: route size is the key distinguishing factor, and the other features of the distribution matter little. Within each capacity the four families give similar ratios (Prefill + Center between 0.102 and 0.117 at Q = 25, between 0.137 and 0.155 at Q = 50 and between 0.200 and 0.243 at Q = 200), whereas the ratios change clearly with route size. As in Table 1, Prefill + Center costs a little against Prefill alone on very short and medium routes (0.111 against 0.092 and 0.144 against 0.138), and the center pays off on ultra-long routes (0.217 against 0.308).

Response to Reviewer bqGb (Part 2/3)

Major 3: Transparency of instance selection

All XML instances of the paper were generated with the original XML generator of Queiroga et al. (2022), the code that produced XML100, with only the number of customers changed. For every instance size, we fixed only the route-size class, which, as stated above, is the most important factor for difficulty, and drew the depot positioning, the customer positioning and the demand distribution at random. We then fixed the number of instances per instance size and route-size class at five, so that every cell of the panel holds the same number of instances, and selected these five at random. To further show that the instances were not deliberately chosen, we also compared vanilla RouteOpt and Prefill + Center on the complete Vrp-Set-X benchmark (100 instances), split by instance size (fewer than 300 customers, and 300 to 1 000 customers) and by route-size class (Table C4).

Table C4. Complete Vrp-Set-X benchmark: geometric-mean root-time ratio. Vanilla median root time: 13 s (fewer than 300 customers) and 228 s (300 to 1 000 customers).

Route-size classFewer than 300 customers300 to 1 000 customersAll
very short0.175 (9/9)0.115 (11/11)0.139 (20/20)
short0.163 (10/10)0.143 (11/11)0.152 (21/21)
medium0.194 (9/9)0.127 (11/11)0.154 (20/20)
long0.270 (9/9)0.164 (12/12)0.203 (21/21)
very long0.325 (6/6)0.237 (12/12)0.263 (18/18)
all0.210 (43/43)0.154 (57/57)0.176 (100/100)

Minor 1: Additional training information

Appendix B lists the architectures, optimizers, schedules and selection rules of the learned components. We add the training time, the computational resources, the training and validation losses and the validation metrics in Table C5, and will include them in the appendix. All models were trained on a single NVIDIA L4 GPU. Because the models are small, training takes only minutes; most of the time goes into obtaining the labels. The data are the 320 labeled XML instances of Appendix B, split into 200 training, 60 validation and 60 test instances.

Table C5. Training of the deployed models. Times are wall-clock on one NVIDIA L4. Train and validation losses are those of the selected checkpoint.

ComponentParametersTraining timeSelection ruleSelected epoch / epochs runTrain lossValidation lossValidation metricTest metric
Edge scorer (graph neural network)1.43 M553 sbest validation Spearman correlation, no early stopping158 / 2600.0126–Spearman 0.489, AUC 0.828Spearman 0.439, AUC 0.770
Dual-center direction (set transformer)424 k69 sbest validation cosine after the box projection, patience 2944 / 740.02260.0246cosine 0.978cosine 0.975

For both models the checkpoint is selected on the validation split. The validation Spearman correlation of the edge scorer peaks at epoch 158 and then declines, and the validation loss of the center rises after epoch 44, while both training losses keep falling; the deployed checkpoints therefore sit just before the onset of overfitting. The center was selected from a sweep over architectures and seeds that took about 56 minutes on the same L4.

Response to Reviewer bqGb (Part 3/3)

Minor 2: Comparison with multi-threaded CPU exact pricing

Original Bucket: RouteOpt's bucket-graph labeling. Batched Bucket: our proposed GPU-friendly bucket graph with batched dominance tests.

Table C6. Median seconds per steady-state exact pricing call, re-measured on the same controlled device.

InstanceRoute sizeOriginal Bucket, 1 CPU threadBatched Bucket, 1 CPU threadBatched Bucket, 16 CPU threadsBatched Bucket, NVIDIA RTX PRO 6000 Blackwell
XML500_1131_01very short0.2130.1180.0900.039
XML500_1132_01short0.4000.8020.2870.071
X-n957-k87medium0.5165.651.550.182
X-n327-k20long0.5583.520.7990.101
XML500_3125_01very long1.308.941.940.270
X-n1001-k43very long9.32106.521.01.30
XML400_1136_01ultra long2.5023.94.830.441
XML500_1126_01ultra long3.8635.76.560.655

In a pure CPU comparison, Batched Bucket has no advantage, which is easy to understand. With the sequential dominance test, a label is deleted as soon as it is found to be dominated, whereas the batched test must wait until the dominance test of a whole wave is complete, so labels that are already dominated keep accumulating in the meantime. Accordingly, on small waves Batched Bucket wins even on one thread (0.118 s against 0.213 s on XML500_1131_01).

References

  • [1] Berto, F., Hua, C., Zepeda, N. G., et al. RouteFinder: Towards foundation models for vehicle routing problems. Transactions on Machine Learning Research, 2025.
  • [2] Zhou, J., Wu, Y., Song, W., et al. Towards omni-generalizable neural methods for vehicle routing problems. ICML, 2023.
Reviewer_bAGuOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies initialization and pricing for the first, cut-free root column-generation solve inside an exact branch-price-and-cut solver. A learned edge scorer guides the construction of feasible CVRP routes, which are held in an external pool rather than dumped into the initial restricted master. Columns are selected at a smoothed dual and checked for admission at the raw dual. A second model initializes the Wentges smoothing center, after which the solver’s own certified updates continue. A GPU bucket-graph labeling backend accelerates exact pricing, with CPU repricing and terminal CPU certification.

The main empirical result is a geometric-mean root-time ratio of 0.132 relative to vanilla RouteOpt over 95 instances, reaching the same certified root bound; prefilling alone gives 0.261. The appendix contains heuristic, preloading, optimal-support, center, and GPU controls. A scheduling experiment also benefits from prefilling and a learned center, but it does not transfer the full learned-routing/GPU pipeline. The reported certification and speedups concern the root relaxation, not complete integer-solve time.

Critical strengths
  1. The improvements are large and consistent against a strong implemented baseline. In Table 1, both prefilling and the full pipeline are faster on all 95 instances. Their geometric-mean ratios, 0.261 and 0.132, are substantial while preserving the certified root bound. The appendix includes raw-instance results and relevant heuristic and oracle controls, so this is not just a comparison against a minimal column-generation routine.

  2. Learning is used in a way that preserves the solver’s correctness contract. The learned route pool and center influence search, but neither supplies the final certificate. Appendix A distinguishes valid elementary prefill columns from exact ng-route pricing; Appendix C specifies raw-dual checks and a terminal CPU exact call. The optimal-support example also gives a meaningful explanation for why apparently excellent warm-start columns need not produce an efficient dual trajectory. This combination of mechanism and solver integration is a strong part of the paper.

Critical weaknesses
  1. The controls establish the pipeline more clearly than the necessity of its learned components. Appendix D does compare learned and HGS pools, and learned and permuted centers. However, the learned pool uses a different constructor, coverage bias, local search, and four parallel seeds, while the HGS pool uses one run and seed. The observed advantage does not isolate the neural edge scores. The lazy-admission argument is also stronger than its main comparison: PDUMP/PN is 1.044 with a 90% interval of [0.960, 1.135]. Finally, Prefill+Center has a ratio of 0.264 versus 0.261 for Prefill alone. These results do not negate the main speedup, but they leave open which learning and admission choices are actually required.

  2. The practical timer boundary needs to be explicit for each headline arm. The appendix reports pool-generation and center-inference costs, and B.1.2 explicitly says that the heuristic pool’s generation time is included in the Appendix D.1 comparison. It would therefore be wrong to say that preparation is entirely unreported. It is still unclear whether the headline root times consistently include feature construction, inference, pool generation/merging/loading, GPU initialization, and terminal CPU re-proof. Table 2 intentionally measures steady-state exact-pricing calls without LP solves; that is useful kernel evidence, but not an inclusive from-instance runtime. Since the system includes both learned preparation and additional hardware, this distinction matters to the practical comparison.

Questions for authors
  1. What are the start and stop points for the timers in Tables 1, 3, and 11? Please state which preparation and certification costs are included and give representative inclusive times starting from the instance file. This is a clarification request, not an assertion that these costs were omitted.

  2. With the same constructor, four-seed execution, and generation budget, how much does learned heat improve over nonlearned scores? How does the HGS pool compare under similar resources? This would separate the learning contribution from the construction procedure.

  3. What is the Prefill+GPU result without the learned center? Under prefill, how do learned, permuted, and standard center initializations compare with the same fallback rules? The center-only controls are helpful, but do not directly establish its contribution to the full pipeline.

I do not view the absence of whole-tree experiments as a separate rejection argument: the paper explicitly acknowledges its cut-free root scope. The claims should simply retain that scope rather than imply faster certified integer solutions.

3 comments

Response to Reviewer bAGu (Part 1/2)

We thank the reviewer for the careful reading and the precise questions, which helped us sharpen what the paper claims and what it measures.

W1: Necessity of the learned components

Learning benefits our pipeline in two ways. First, the initial columns do not need to be exactly right, so learning offers a faster and more efficient way to construct them. Second, the natural target is not the best start: preloading the support of the converged root LP, the best columns one could know in advance, is the slowest arm of Appendix D.1, whereas a rich neighborhood of near-optimal routes works best. Such a target is hard to specify by hand, and learning captures it well.

On HGS: HGS was not designed for this task; its purpose is to iterate toward an optimal set of routes. We identified that its design matches what we expect from initial columns (see also the comparison with other heuristics in our response to Reviewer 8oVY, W2). To use HGS we record part of the columns along its search and limit the time or the maximum number of columns, which leaves too many parameters to control. We therefore built a constructor designed entirely for our task, driven by edge scores and matching the coverage we expect. Because it is built for this task, it runs within one second on most instances, even with 1 000 customers.

On the constructor alone: Table D1 compares our learned constructor with a constructor driven by random edge scores.

Table D1. Root time with our learned constructor and with a random-score constructor, 115 instances; geometric-mean ratio to our solver with every component switched off, same job and node; in parentheses, the number of instances faster than that base.

Route-size classInst.Learned (ours)Random scores
very short200.097 (20/20)0.301 (20/20)
short200.136 (20/20)0.371 (20/20)
medium200.196 (20/20)0.550 (19/20)
long200.288 (20/20)0.610 (20/20)
very long200.364 (20/20)0.649 (19/20)
ultra long150.416 (15/15)0.509 (15/15)
all1150.214 (115/115)0.480 (113/115)

Random scores are 2.24 times slower, and our learned constructor is faster on 113 of the 115 instances. Random scores also benefit from the constructor, which aims at diversity and coverage: even with random scores, the root time is 0.480 of the base.

On lazy admission: on the same ten ultra-long instances as Table D4, preloading the learned pool into the initial master instead of admitting it lazily makes the root 1.56 times slower in geometric mean, and slower on all ten instances. Adding the columns gradually also acts, to some extent, as a slight further smoothing of the dual.

W2: Timer boundary

Because our constructor is built for collecting columns, the process is controllable and fast. Our timing includes every step, from feature construction and model prediction to the terminal CPU re-proof. This preparation is cheap, partly because each model predicts only once per instance, Prefill + Center depends little on the GPU, and the models are small (1.4 M parameters for the edge scorer and 0.4 M for the center).

Q1: Start and stop points of the timers

The times in Tables 1 and 11 cover every step from the instance file to the converged root: feature construction, model prediction, pool generation, loading the pool and the center, GPU initialization, root column generation and the terminal CPU re-proof. Table 3 (scheduling) reports the wall time of root column generation until the bound is certified. Typical times of the main steps are:

StepTime per instance
Learned pool generation (features, edge scorer, construction, writing the pool)median 0.20 s, at most 0.36 s
Center inference (features, networks, trees, writing the center)median 0.13 to 0.18 s, at most 0.71 s
GPU initializationfirst exact call, initialization included: median 0.42 s
Terminal CPU re-proofmedian 0.70 s, at most 8.8 s (median 6 % of the root time)

Q2: Learned scores, the constructor and HGS

First, Table D1 (W1) compares our learned constructor with a random-score constructor: random scores are 2.24 times slower.

Second, HGS is designed to search for an optimal solution, not to produce initial columns. In our experiments the HGS pool is generated within 60 s per instance; Tables B1 and B2 of our response to Reviewer 8oVY report the result of placing it directly into the initial master.

Overall, the learned scores play a role, and the performance of the constructor itself plays a key role. HGS was never meant to produce initial columns, so it is understandable that it needs more generation time and accelerates the root less.

Response to Reviewer bAGu (Part 2/2)

Q3: Prefill + GPU without the learned center

The key of our pipeline is the compression of heuristic pricing. Table D2 gives the mean share of root time per pricing level: prefill mainly compresses the LIGHT level and the center mainly compresses HEAVY. Prefill alone still leaves 55 % of the root time in heuristic pricing (LIGHT and HEAVY), against 39 % for Prefill + Center, which is why the center pays off once exact pricing is accelerated.

Table D2. Mean share of root time per pricing level on the panel.

ConfigurationLIGHTHEAVYEXACT
Vanilla64 %21 %15 %
Prefill34 %21 %45 %
Center68 %3 %29 %
Prefill + Center34 %5 %61 %

Table D3 adds Prefill + GPU, without the learned center, next to Prefill, Prefill + Center and the full pipeline, in the layout of Table 1.

Table D3. Geometric-mean root-time ratio on the 95 instances of Table 1; ratio to our solver with every component switched off; in parentheses, the number of instances faster than that base.

SetClassInst.PrefillPrefill + GPUPrefill + CenterFull pipeline
Xshort50.129 (5/5)0.117 (5/5)0.142 (5/5)0.113 (5/5)
Xmedium50.181 (5/5)0.131 (5/5)0.194 (5/5)0.118 (5/5)
Xlong50.291 (5/5)0.159 (5/5)0.266 (5/5)0.113 (5/5)
Xvery long50.329 (5/5)0.239 (5/5)0.302 (5/5)0.150 (5/5)
Xall200.217 (20/20)0.156 (20/20)0.217 (20/20)0.123 (20/20)
XML300short50.196 (5/5)0.150 (5/5)0.209 (5/5)0.140 (5/5)
XML300medium50.280 (5/5)0.195 (5/5)0.301 (5/5)0.157 (5/5)
XML300long50.278 (5/5)0.209 (5/5)0.260 (5/5)0.189 (5/5)
XML300very long50.448 (5/5)0.318 (5/5)0.407 (5/5)0.228 (5/5)
XML300ultra long50.377 (5/5)0.314 (5/5)0.287 (5/5)0.258 (5/5)
XML300all250.303 (25/25)0.227 (25/25)0.286 (25/25)0.189 (25/25)
XML400short50.161 (5/5)0.125 (5/5)0.171 (5/5)0.109 (5/5)
XML400medium50.236 (5/5)0.155 (5/5)0.226 (5/5)0.124 (5/5)
XML400long50.321 (5/5)0.218 (5/5)0.280 (5/5)0.136 (5/5)
XML400very long50.377 (5/5)0.227 (5/5)0.374 (4/5)0.188 (5/5)
XML400ultra long50.457 (5/5)0.334 (5/5)0.384 (5/5)0.196 (5/5)
XML400all250.291 (25/25)0.200 (25/25)0.274 (24/25)0.147 (25/25)
XML500short50.125 (5/5)0.088 (5/5)0.134 (5/5)0.071 (5/5)
XML500medium50.158 (5/5)0.125 (5/5)0.160 (5/5)0.097 (5/5)
XML500long50.228 (5/5)0.144 (5/5)0.229 (5/5)0.110 (5/5)
XML500very long50.358 (5/5)0.215 (5/5)0.408 (4/5)0.172 (5/5)
XML500ultra long50.370 (5/5)0.266 (5/5)0.289 (5/5)0.209 (5/5)
XML500all250.226 (25/25)0.155 (25/25)0.225 (24/25)0.122 (25/25)
all950.259 (95/95)0.184 (95/95)0.251 (93/95)0.144 (95/95)

Prefill runs with standard Wentges smoothing by default, with the parameters of Table 4 in the appendix. Under prefill, Table D4 compares the standard, permuted and learned center initializations with the same fallback rules on the ten ultra-long XML400 and XML500 instances, where the effect of the dual center is most visible. The permuted center (CRAND, Appendix D.2) is on average no better than standard smoothing, so the gain comes from the learned direction.

Table D4. Root time in seconds on the ten ultra-long instances.

InstancePrefill (standard Wentges)Prefill + permuted centerPrefill + learned center
XML400_1136_01289256212
XML400_1226_01283279229
XML400_1346_01273296244
XML400_2366_01216298160
XML400_3356_01241288224
XML500_1126_019701 220621
XML500_1176_01596531361
XML500_1276_011 3461 1341 059
XML500_1346_011 7301 3461 216
XML500_3266_011 8272 0811 750

Dear Reviewer bAGu,

Thank you again for your careful reading of our paper and for your detailed and insightful review. As the discussion period ends on November 18 (AoE), we would like to kindly check whether our response has addressed your concerns. If any question remains, we would be glad to clarify it while the discussion window is still open.

In addition, we would like to highlight one point about our idea of systematically reducing heuristic pricing, which Table D3 of our response shows most clearly through the Prefill + GPU column. With CPU pricing, Prefill + Center is no faster than Prefill on several classes, mainly those with short and medium routes. With GPU pricing, however, the two together reduce heuristic pricing further and push the work towards exact pricing, so that Prefill + Center + GPU, our full pipeline, is the fastest configuration in every class of every instance set. Over all 95 instances, the learned center improves Prefill only from 0.259 to 0.251, but Prefill + GPU from 0.184 to 0.144. We will strengthen the discussion of this point in the revised version, to help readers better understand how the components work together.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.