- 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
- The observation that imperfect columns help more than optimal ones is an interesting and innovative idea.
- 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
- There isn't a full-tree evaluation, it isn't clear how the speedup translates to solving the complete instance.
- 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
- 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?
- Have you evaluated zero-shot generalization on CVRP instances from different distributions or size ranges, without retraining?
5 comments
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 = opt | UB = BKS + 1 | |||||
|---|---|---|---|---|---|---|
| Instance | Vanilla | Full pipeline | Full / vanilla | Vanilla | Full pipeline | Full / vanilla |
| X-n101-k25 | 2.0 (1) | 1.0 (1) | 0.49 | 2.3 (1) | 1.0 (1) | 0.43 |
| X-n106-k14 | 25 (1) | 11 (1) | 0.42 | 26 (1) | 12 (1) | 0.47 |
| X-n110-k13 | 4.7 (1) | 2.8 (1) | 0.60 | 5.0 (1) | 2.8 (1) | 0.57 |
| X-n115-k10 | 29 (1) | 19 (1) | 0.65 | 31 (1) | 25 (1) | 0.81 |
| X-n120-k6 | 793 (7) | 448 (5) | 0.56 | 1 057 (9) | 488 (7) | 0.46 |
| X-n125-k30 | 49 (3) | 66 (3) | 1.36 | 51 (3) | 46 (3) | 0.90 |
| X-n129-k18 | 85 (3) | 58 (3) | 0.68 | 57 (3) | 59 (3) | 1.04 |
| X-n134-k13 | 1 752 (19) | 2 207 (33) | 1.26 | 2 157 (31) | 1 578 (19) | 0.73 |
| X-n139-k10 | 115 (1) | 173 (1) | 1.50 | 110 (1) | 182 (1) | 1.66 |
| X-n143-k7 | 6 170 (53) | 3 240 (33) | 0.53 | 6 161 (53) | 2 858 (27) | 0.46 |
| X-n148-k46 | 3.3 (1) | 2.6 (1) | 0.79 | 5.6 (1) | 3.1 (1) | 0.55 |
| X-n153-k22 | 446 (13) | 340 (19) | 0.76 | 436 (13) | 260 (13) | 0.60 |
| X-n157-k13 | 19 (1) | 14 (1) | 0.75 | 24 (1) | 16 (1) | 0.68 |
| X-n162-k11 | 946 (5) | 558 (3) | 0.59 | 1 549 (5) | 608 (3) | 0.39 |
| X-n167-k10 | 424 (1) | 217 (1) | 0.51 | 370 (1) | 195 (1) | 0.53 |
| X-n172-k51 | 110 (3) | 60 (3) | 0.54 | 87 (5) | 79 (3) | 0.91 |
| X-n176-k26 | 126 (7) | 82 (9) | 0.65 | 117 (5) | 91 (9) | 0.78 |
| X-n181-k23 | 131 (9) | 101 (9) | 0.78 | 160 (11) | 152 (15) | 0.95 |
| X-n186-k15 | 8 478 (97) | 4 296 (69) | 0.51 | 9 760 (95) | 3 285 (61) | 0.34 |
| X-n195-k51 | 60 (5) | 43 (7) | 0.72 | 67 (7) | 51 (5) | 0.77 |
| X-n200-k36 | 586 (59) | 498 (47) | 0.85 | 693 (91) | 599 (57) | 0.86 |
| Geometric mean | 0.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).
| Group | Inst. | Q = 25: Prefill+Center | Q = 25: Full pipeline | Q = 50: Prefill+Center | Q = 50: Full pipeline | Q = 200: Prefill+Center | Q = 200: Full pipeline |
|---|---|---|---|---|---|---|---|
| U | 10 | 0.117 (10/10) | 0.096 (10/10) | 0.137 (10/10) | 0.089 (10/10) | 0.219 (10/10) | 0.147 (10/10) |
| C | 10 | 0.112 (10/10) | 0.097 (10/10) | 0.137 (10/10) | 0.089 (10/10) | 0.243 (10/10) | 0.146 (10/10) |
| M | 10 | 0.115 (10/10) | 0.101 (10/10) | 0.155 (10/10) | 0.106 (10/10) | 0.200 (10/10) | 0.117 (10/10) |
| E | 10 | 0.102 (10/10) | 0.086 (10/10) | 0.148 (10/10) | 0.099 (10/10) | 0.207 (10/10) | 0.129 (10/10) |
| n = 300 | 20 | 0.115 (20/20) | 0.111 (20/20) | 0.165 (20/20) | 0.117 (20/20) | 0.239 (20/20) | 0.154 (20/20) |
| n = 500 | 20 | 0.107 (20/20) | 0.081 (20/20) | 0.126 (20/20) | 0.078 (20/20) | 0.197 (20/20) | 0.117 (20/20) |
| all | 40 | 0.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.
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.