Metraipolis › archive › dc_2f083a91f693

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.21001
License (as archived)
CC0-1.0
Archived
2026-10-16T10:20:07.780Z
SHA-256 of the archived text
d7669e0a943f4598f58bec7ca13997c04856f0398e70ce702048938590f8715f
Stable URL of this page
https://metraipolis.com/documento/dc_2f083a91f693

How to cite

Imperfect Is Perfect: Learned Column Prefilling for Branch-Price-and-Cut — arXiv:2610.21001 — arXiv (en), https://arxiv.org/abs/2610.21001 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2f083a91f693 (Metraipolis archive dc_2f083a91f693, sha256 d7669e0a943f4598f58bec7ca13997c04856f0398e70ce702048938590f8715f)
BibTeX
@misc{dc2f083a91f693,
  title = {Imperfect Is Perfect: Learned Column Prefilling for Branch-Price-and-Cut — arXiv:2610.21001},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.21001},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2f083a91f693; sha256 d7669e0a943f4598f58bec7ca13997c04856f0398e70ce702048938590f8715f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.21001. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.21001 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T08:48:02.672Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).