Reinforcement learning speeds up solving large linear programs
Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming
Artificial IntelligenceMachine Learning
Summary
Large linear programs are complex mathematical problems used in many fields, but solving them quickly can be difficult. The authors created GALLOP, a method that uses reinforcement learning to improve the efficiency of a popular solving technique called primal-dual hybrid gradient (PDHG). GALLOP learns how to set algorithm parameters and decide when to restart calculations to speed up solving without needing complicated adjustments. In tests, GALLOP solved problems much faster and worked well on bigger problems than it was trained on.
What this means in practice
- •For operations research teams: Speed up large-scale optimization tasks by using learned policies to accelerate primal-dual algorithms without manual tuning.
- •For data center operators: Reduce computation time and energy usage when solving high-dimensional linear programs integral to resource allocation and logistics.
Authors
Jinhwan Sul, Alex Oshin, Evangelos A. Theodorou
Abstract
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.