CS Paper Radar

Learning Warm Starts for the Simplex Method from Measured Solver Cost

Felix Parker, Danielle A. Ripsman, Emmett Springer, Kimia Ghobadi

cs.LG math.OC ·submitted 2026-10-14 20:19 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

AHEAD: Adaptive Neural Acceleration for Large-Scale Linear Programming

cs.LG math.OC ·2026-10-26 ·Sihao Liu, Zhichao Hou, Huayue Gu, Raiyan Rahman, Liang Wu +2 more
similarity 0.68
Abstract

Large-scale linear programs with millions of variables and constraints strain time and memory budgets. First-order methods such as the primal-dual hybrid gradient scale to this regime because they avoid matrix factorizations, but they require many iterations. Learned accelerators can reduce these iterations, yet fewer iterations do not guarantee a shorter solve. Learning inference also takes time, and running the accelerator longer trades solver time for inference time. Existing unrolled accelerators handle this trade-off poorly: each layer processes every variable and constraint, the predicted iterates still need solver refinement, and every instance runs the same layers. We therefore ask: What neural accelerator design achieves end-to-end speedups on large-scale linear programs across sizes and target accuracies? We introduce AHEAD, an accelerator that predicts step sizes for first-order linear programming solvers while keeping their update rules. Its weight-shared predictor reads compact solver statistics and rescales the primal and dual step sizes, so each warm-start iteration stays inexpensive and a short warm-start phase hands the solver a warm start. A learned handoff policy sets the number of warm-start iterations for each instance and target accuracy, after which the solver finishes under its own termination criterion. On packing linear programs with up to $10^7$ variables, AHEAD achieves $6.5$--$11.6\times$ end-to-end speedups over Gurobi's first-order solver from a cold start, including on instances of unseen sizes and distributions. The gains extend to PageRank linear programs and hold across difficulty levels and target accuracies.

0.18

Imperfect Is Perfect: Learned Column Prefilling for Branch-Price-and-Cut

cs.LG ·2026-10-14 ·Haoran Liu, Yu Yang
benchmark similarity 0.60
Abstract · 27 pages, 3 figures

Column generation folklore warns that initial columns hurt: a warm start may bias the dual and slow the root of branch-price-and-cut. We show the opposite once the columns are imperfect in the right way. Preloading the support of the optimal root LP, the best columns one could know in advance, fails to finish on half of our hardest instances; a pool of ordinary routes that need not belong to any optimal solution, held outside the master and priced at the current smoothed dual, speeds the root up. Because the columns need not be optimal, producing them becomes a learning task: a neural edge scorer guides a constructive generator that builds the pool in seconds. A second network predicts the initial center of Wentges smoothing from the instance file, and with it the direction of the smoothed pricing queries; the solver's own updates run unchanged. With prefill and center in place, exact pricing dominates root pricing time, so we rebuild bucket-graph labeling around its dominance test for the GPU and certify on the CPU. Inside RouteOpt, the state-of-the-art exact solver for capacitated vehicle routing, the pipeline reaches the same certified root bound in 13.2% of vanilla RouteOpt's root pricing time over 95 instances with 300 to 1000 customers, prefill alone in 26.1%, and 17.5 times faster in the best case. In an exact branch-price-and-cut solver for unrelated parallel machine scheduling, prefill with smoothing and the learned center certifies all 25 benchmark instances, 12 times faster than the solver's own column generation, which certifies 20 of them.

0.50

An Analytical Model of Compute-limited Multistage Training Pipelines

cs.LG ·2026-11-09 ·Nishil Patel, Jin Hwa Lee, Basile Confavreux, Andrew Saxe
top venue similarity 0.59
Abstract · Accepted at NeurIPS 2026

Modern foundation models are trained through multiple stages, yet how these stages interact and how compute should be allocated across them remain poorly understood. We introduce an analytically tractable high-dimensional model combining unsupervised pretraining with a linear autoencoder, supervised fine-tuning (SFT) with noisy stepwise labels, and reinforcement learning (RL) with sparse episodic rewards. Using random matrix theory and an operator-projection closure, we derive approximate low-dimensional learning dynamics that closely match simulations. We show that finite pretraining data imposes a representation-dependent performance limit, with Bayes classification error scaling as the inverse square root of the pretraining sample ratio, and observe the same exponent in asymptotic SFT and RL errors. Better pretraining also reduces sensitivity to noisy supervision. SFT initialization shortens the initial RL plateau induced by sparse rewards, an effect we also observe in OLMo-2 1B on GSM8K. Longer SFT warm starts additionally improve asymptotic RL performance. Optimizing compute across all three stages reveals that the optimal allocation depends on supervision quality and total budget, with a non-monotonic dependence of the RL compute share on budget. Finally, a complementary compositional model shows how RL selectively strengthens task-relevant pretrained skills while largely preserving unused skills. Together, these results identify mechanisms linking representation quality, feedback structure, and compute allocation in multistage training.

0.23

Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming

cs.AI math.OCcs.LG ·2026-10-01 ·Jinhwan Sul, Alex Oshin, Evangelos A. Theodorou
benchmark similarity 0.59
Abstract · 35 pages, 4 figures

Primal-dual hybrid gradient (PDHG) methods solve large-scale linear programs (LPs) using GPU-friendly matrix-vector products and projections, but their practical performance depends on coordinating algorithm parameters, acceleration, and restarts. We introduce GALLOP, which uses reinforcement learning to jointly learn continuous algorithm parameters and discrete restart decisions without differentiating through the solver. Its generalized accelerated PDHG update combines separate primal and dual extrapolation, history corrections, and restart anchoring with independently adjustable coefficients. We train a dimension-agnostic feedback policy using a groupwise proximal policy optimization objective that clips likelihood ratios separately for different control groups and excludes inactive acceleration controls on restart transitions. We evaluate GALLOP on six LP families and a public item-placement benchmark. On the main evaluation settings across the six families, GALLOP reduces iteration counts by factors of $1.9$-$5.6$ and achieves up to a $16.0\times$ speedup in algorithm wall-clock time over MPAX. With one policy trained per family, the learned policies generalize without retraining to within-family LPs $3\times$-$400\times$ larger than the largest training instances, including Transport LPs with $10.24$ million variables.

0.28

Zero-Shot Weight-Space Programming for Prediction and Classification of Target Variables in Structured Datasets

cs.AI ·2026-11-14 ·Eduardo C. Garrido-Merchán
similarity 0.58
Abstract

Weight-space programming fixes every parameter of a feed-forward network by hand, with no gradient descent anywhere in the construction. Every demonstration so far starts from a target function handed to the model as a rule system, making it a compilation problem. A supervised dataset withholds that specification, so the procedure must do the statistical inference itself and then express the result in the parameterisation it was given. We ask whether a large language model can do both. It is shown a small dataset in full, with the architecture of a feed-forward network, and writes out every weight and bias as a literal number, with no optimizer, no gradient, no code execution, and no chance to evaluate it first. Each construction is sealed and pre-registers its expected score. The graded suite runs from two toy problems, through nine synthetic problems disguised by a hidden rotation, to the classical benchmarks and one real engineering regression. The frozen network matches the closed-form optimum wherever that optimum is linear, reaches the irreducible error of the generating process on three rungs where it is not, and beats every fitted baseline on two of those, including the same architecture trained by gradient descent. It fails on two rungs, both times because the structure to be found is oblique to the coordinates it analysed. Three further constructors separate two failure modes a single score conflates: one returns no parameter vector at all on the hardest rungs, another delivers everywhere while writing networks worse than predicting the mean. One of those failures proves avoidable: another constructor solves the oblique-hinge rung by a margin that survives multiple-comparison correction. What predicts whether the hidden layer earns its keep is the training error of a linear separator, which the composite complexity index misses.

0.17

Predictive Dual Smoothing for Column Generation

cs.LG cs.AI ·2026-09-28 ·Senne Berden, Noah Schutte, Andrea Lodi, Tias Guns
similarity 0.57
Abstract

Solving large-scale linear programs efficiently is an important challenge in many optimization settings. A key technique is column generation, which alternates between solving the master problem over a restricted subset of the variables, and using a pricing subproblem to identify new variables to add. The pricing subproblem is guided by the dual solution of the current restricted master problem, but oscillations in these dual solutions can substantially slow convergence. Dual stabilization methods address this issue. Dual smoothing is a common stabilization method, which guides the pricing subproblem using a combination of the current dual solution and duals from previous iterations. However, while past dual solutions can stabilize the dual trajectory, they do not necessarily guide pricing towards useful new variables. We therefore introduce predictive dual smoothing, which instead combines the current dual solution with a learned prediction of future duals to steer pricing towards variables that are more useful in subsequent iterations. The predictor is trained offline using supervision extracted from standard column generation trajectories and is used only to modify the pricing subproblem's objective function, while exact reduced-cost checks and fallback pricing with the unsmoothed duals preserve correctness. Experiments on cutting stock and generalized assignment problems show that predictive dual smoothing substantially reduces generated columns and wall-clock time relative to standard column generation and existing classical and learned stabilization methods. These gains extend to out-of-distribution instance sizes, and predictive smoothing provides further improvements when combined with strong classical stabilization.

0.25

Just sort it! A note on the LP behind rank-one anti-loop edits

cs.LG cs.CLmath.OC ·2026-11-16 ·Matteo Fischetti
similarity 0.57
Abstract · 4 pages, 3 tables. Data, code and protocols: https://doi.org/10.5281/zenodo.24286137

Weight-space programming removes the thinking loops of a small reasoning model by a rank-one edit W' = W + u v^T of an MLP output matrix, where u is a loop direction and v is the solution of a sparse Linear Program (LP) over the neuron activations. We investigate whether the LP is needed. We replace it by a sort: we take the 8 neurons whose activation has the smallest coefficient of variation, and give them equal shares of the push that the LP solution realizes. On Qwen3.5-0.8B the sorted edit scores 67.0% on 1000 problems (MATH-500 and GSM8K) against 67.4% for the LP edit and 9.5% for the unedited model; the paired difference is -0.4 points, with 95% confidence interval [-2.9, +2.1], inside a non-inferiority margin of 5 points declared before the runs. On three further sampling seeds the difference is -0.6 points, interval [-2.0, +0.8], and -0.8 points, interval [-2.3, +0.6], when the dose is set without the LP. The sort does not solve the LP, but the neurons it shares with the LP solution carry most of its mean push. The outcome is that, on this model, the edit acts as a nearly constant bias along u.

0.36

Cost-Accuracy Trade-offs: Neural Operator vs Classical Numerical Solver

cs.LG math.NA ·2026-09-21 ·Daniel Zhengyu Huang, Andrew M. Stuart
benchmark similarity 0.57
Abstract · 41 pages; 10 figures

Neural operators are data-driven models that learn mappings from inputs that parameterize partial differential equations, such as spatially varying coefficients, initial conditions, forcing terms, boundary conditions, or geometries, to solution fields or quantities of interest. Once trained, they can serve as surrogates for classical numerical solvers in many-query settings that require repeated evaluations for varying inputs. We address the question of when, and then why, neural operator surrogates outperform classical numerical solvers, in terms of cost for a given accuracy. We focus on the post-training, many-query limit, in which data-acquisition and training costs are treated as fixed and fully amortized. Even in this deliberately favorable regime for neural operators, there are regimes in which classical solvers outperform the surrogate models. We compare the cost-accuracy performance of neural operator surrogates and classical numerical solvers through a reproducible benchmark study comparing neural operators with problem-matched classical solvers on representative problems in computational science and engineering, focusing on prediction error, per-query floating-point cost, and wall-clock runtime. Neural operators are most competitive at low-to-moderate accuracy requirements. Their floating-point cost advantage depends strongly on the problem structure, arising when they avoid temporal or nonlinear iterations or predict a reduced quantity of interest rather than a full solution field. Additional wall-clock speedups result from dense tensor operations that are well suited to modern hardware. As the target accuracy is tightened, achieving the required accuracy with neural operators becomes increasingly challenging, and classical solvers outperform surrogates in this regime; thus classical solvers will remain important for verification and high-accuracy computation.

0.45