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

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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Optimization & Control

• arXiv preprint · 1 October 2026

  Mean field games as a tool for AI safety: a worked example from the July 2026 Hugging Face incident

  P. Jameson Graber
• arXiv preprint · 2 October 2026

  A hybrid CNN-adjoint optimization framework for reconstruction of viscoelastic tissue properties in magnetic resonance elastography

  Anwesa Dey, Johann Rudi and Elena Cherkaev
• arXiv preprint · 1 October 2026

  OR for AI That Does OR: Routing LLMs up the Escalator inside the OSCAR Framework

  Jinzhi Bu, Haixin Tang and Huanan Zhang
• arXiv preprint · 2 October 2026

  Distributed Learning with Selective State Space Models: Architecture-Aware Convergence Analysis

  Adam Piaseczny, Md Kamran Chowdhury Shisher, Shiqiang Wang and 1 other
• arXiv preprint · 1 October 2026

  Initial condition recovery in nonlinear damped viscous photoacoustic tomography using a convolutional neural network-guided gradient-free optimization framework

  Madhu Gupta, Anwesa Dey, Prapti Tala and 1 other

All new papers in Optimization & Control