Learning Warm Starts for the Simplex Method from Measured Solver Cost

arXiv:2610.20892v1 Announce Type: cross 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.

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.

Optimization and Control (math.OC); Machine Learning (cs.LG)

arXiv:2610.20892 [math.OC]

(or arXiv:2610.20892v1 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2610.20892 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.

aiqbench analysis

Learning Warm Starts for the Simplex Method from Measured Solver Cost

Related coverage