aiqbench analysis
This paper uses learned components, a neural edge scorer for generating initial columns and a network that predicts the Wentges smoothing center, to speed up exact branch-price-and-cut solvers for vehicle routing and parallel machine scheduling. The reported gains are relative to the authors' own baselines on specific benchmark sets, so they are best read as evidence for this hybrid approach rather than a general claim about ML-accelerated optimization. For ML readers, the useful takeaway is the design pattern: learned models that produce non-optimal but well-chosen warm-start data, paired with solver internals left unchanged for certification.
Imperfect Is Perfect: Learned Column Prefilling for Branch-Price-and-Cut
arXiv:2610.21001v1 Announce Type: new Abstract: Column generation folklore warns that initial columns hurt: a warm start may bias the dual and slow 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 times 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 times faster than the solver's own column generation, which certifies 20 of them.
Abstract:Column generation folklore warns that initial columns hurt: a warm start may bias the dual and slow 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 times 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 times faster than the solver's own column generation, which certifies 20 of them.
Machine Learning (cs.LG)
arXiv:2610.21001 [cs.LG]
(or arXiv:2610.21001v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.21001 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 349 words
Related coverage
The Entangled Dimensions of Decision Theory
LessWrong · Jul 30, 2026
[AINews] Gemini 4 Argon: GDM’s answer to Astra/Fable, with 1M output
Latent Space · Oct 1, 2026
Expenditure Horizon: Measuring Optimization Ability, with an Application to NanoGPT
METR · Jul 21, 2026
Coverage-driven alignment - What ‘Teaching Claude Why’ can borrow from AV verification
LessWrong · Jun 8, 2026