Learning Warm Starts for the Simplex Method from Measured Solver Cost

Learned initial bases for the simplex method predict which variables are basic at optimality, before handing the resulting basis to an off-the-shelf solver. Prior work has shown that while solutions built from a well-tuned GNN-based architecture can successfully reduce iteration-count, the time they save may fall well short of the iterations they save. 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 the 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, and 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 show that on 25 classes of linear programs, a strong supervised basis predictor removes two thirds of the iterations of the HiGHS dual simplex but only a third of its time. 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, or no warm start. On unseen LPs of the training classes, including LPs four times the training size, CostStart roughly halves the solve time of HiGHS and is 1.4 to 2.2 times as fast as two published methods retrained on the same data.