Learning Warm Starts for the Simplex Method from Measured Solver Cost
Abstract
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.
Related
- A Feasible-Direction-Type Method for Nonconvex Optimization with Infeasible Starts
- The fixed-point bundle method over product-of-simplex domains arising from game equilibria
- MLegS: A modern mapped Legendre spectral method solver for unbounded domains with parallelization
- A fully convergent fixed-point fast sweeping method with the WENO-JS local solver for steady state of hyperbolic conservation laws
- CuPIQP: A Batched and Differentiable QP Solver on GPUs for Robot Learning and Control
BibTeX
@misc{parker2026learning,
title = {{Learning Warm Starts for the Simplex Method from Measured Solver Cost}},
author = {Felix Parker and Danielle A. Ripsman and Emmett Springer and Kimia Ghobadi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20892},
eprint = {2610.20892},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20892},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Learning Warm Starts for the Simplex Method from Measured Solver Cost
AU - Felix Parker
AU - Danielle A. Ripsman
AU - Emmett Springer
AU - Kimia Ghobadi
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20892
UR - https://arxiv.org/abs/2610.20892
AB - 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.
ER -