arXiv preprint ·
Learning Warm Starts for the Simplex Method from Measured Solver Cost
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
When is a better LLM worth paying for? Stochastic Optimization with Switching Mixed-Fidelity Oracles
On the Optimisation Landscape of Overparameterised Weighted MMD
Honesty is the Best Policy ... or is it? Demand Management for Probabilistic Service Options
An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.