SimplexRL: Learning to Pivot

Methods and Modelsoptimizationmethods
Summary

SimplexRL trains reinforcement-learning agents to choose pivots for the simplex method, learning from the structure of each linear program which variable should enter the basis next. The simplex method solves a linear program by walking from corner to corner of its feasible region, and textbook pivoting rules make each step's choice with a fixed formula, even though that choice decides how long a solve takes.

The project's policies fuse a graph encoding of the linear program with the solver's own signals (reduced costs, basis status and pricing scores), and improve through search: an exact solver acts as a policy-improvement operator whose better decisions are distilled back into the network. Training and benchmarking run on SyntheticLPs.jl, a generator library built for the project that turns a target size, a feasibility status and a random seed into a realistic, reproducible linear program.

A first paper takes on warm starts, deciding where the simplex method begins. Predicting the optimal basis can remove two thirds of the dual simplex's iterations yet only a third of its time, because the iterations a good start removes tend to be cheap. CostStart therefore learns from measured solver cost rather than iteration counts, choosing for each problem how many predicted columns to use, which algorithm and pricing rule to run, and whether to warm-start at all. On unseen problems, including ones four times larger than those it trained on, it roughly halves solve time relative to the solver's default start.

The simplex pivot graph of a linear program as A* search expands it, tracing the shortest pivot path from the starting basis to the optimum (SimplexRL A* Pivot-Graph Visualizer).
The simplex pivot graph of a linear program as A* search expands it, tracing the shortest pivot path from the starting basis to the optimum (SimplexRL A* Pivot-Graph Visualizer).
Live demo

Publications

2026

Learning Warm Starts for the Simplex Method from Measured Solver Cost

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

arXiv:2610.20892

pdfcitedoi