Metraipolis › archive › dc_7773bbd65c29

Learning Warm Starts for the Simplex Method from Measured Solver Cost — arXiv:2610.20892

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.20892
License (as archived)
CC0-1.0
Archived
2026-10-16T10:25:03.123Z
SHA-256 of the archived text
20765f8e4ebf383d0c0b04ad5b3a6b9fd6e2bae91b4c279e3a9c94faf90f0a3d
Stable URL of this page
https://metraipolis.com/documento/dc_7773bbd65c29

How to cite

Learning Warm Starts for the Simplex Method from Measured Solver Cost — arXiv:2610.20892 — arXiv (en), https://arxiv.org/abs/2610.20892 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7773bbd65c29 (Metraipolis archive dc_7773bbd65c29, sha256 20765f8e4ebf383d0c0b04ad5b3a6b9fd6e2bae91b4c279e3a9c94faf90f0a3d)
BibTeX
@misc{dc7773bbd65c29,
  title = {Learning Warm Starts for the Simplex Method from Measured Solver Cost — arXiv:2610.20892},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.20892},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7773bbd65c29; sha256 20765f8e4ebf383d0c0b04ad5b3a6b9fd6e2bae91b4c279e3a9c94faf90f0a3d},
  year = {2026}
}

Archived text

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

Learned warm starts for the simplex method build starting bases using predictions of which variables will be basic at optimality. Prior work has shown that starting bases predicted by graph neural networks can sharply reduce iteration counts, but the time saved may fall well short of the iterations saved. On 25 classes of linear programs (LPs), we find that a strong supervised basis predictor removes two thirds of the dual simplex's iterations but only a third of its time. Two effects explain the gap: the iterations removed by a good start tend to be cheap, and closeness to an optimal basis does not rank starts by cost. We prove that two starts with equal overlap with an optimal basis and equal pivot counts can differ in linear-algebra work by a factor that grows with the square root of the number of rows. Empirically, across the starts of one LP, the pivot count explains 71% of the variance of log solve time, while the CPU instruction count explains 98.5%. We introduce CostStart, which uses supervised prediction for the basis and trains a small policy on measured instruction counts to choose, per LP, how many predicted columns to use, which algorithm and pricing rule to run, and whether to warm-start at all. On unseen LPs of the training classes, including LPs four times the training size, CostStart roughly halves the solve time relative to the solver's default start and is 1.4 to 2.2 times as fast as two published methods retrained on the same data.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.20892 — 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.858Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).