Cost aware warm starts cut simplex solve time by half
Learning Warm Starts for the Simplex Method from Measured Solver Cost
Machine Learning
Summary
Solving certain math problems called linear programs can be sped up by guessing the best starting point — but only if time spent matches iteration gains. The authors found that even good guesses often skip easy steps, so total time savings are less than expected. They measured actual computer work done and trained a system named CostStart to pick starting points and algorithm tweaks based on real cost data. This system reduces solving time roughly by half compared to usual methods, and beats other learning approaches. Their work helps make solving these problems more efficient.
What this means in practice
- •For operations research teams: Speed up solving large linear optimization problems by using learned warm starts optimized for real computational cost.
- •For software engineers building optimization solvers: Integrate CostStart’s cost-based warm start and algorithm configuration to reduce solve times and improve solver efficiency on unseen problem instances.
Authors
Felix Parker, Danielle A. Ripsman, Emmett Springer, Kimia Ghobadi
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.