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× 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×-400× larger than the largest training instances, including Transport LPs with $10.24$ million variables.
Related
- Hamiltonian Primal-Dual Policy Reinforcement Learning for Derivative-Free Model-Based Control
- Safe Multi-Objective Reinforcement Learning: Zero Constraint Violation and Primal-Averaging Convergence
- Continuous Delayed-Memory Stochastic Gradient Descent and Continuous-Time Reinforcement Learning from History of Astrophysical Time Series Studies
- Boundary-aware Reinforcement Learning for Hypercube State Spaces via Deterministic Policy Gradient
- Well-Posedness and Strong Convergence of Infinite-Dimensional Port-Hamiltonian Primal-Dual Gradient Dynamics
BibTeX
@misc{sul2026reinforcement,
title = {{Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming}},
author = {Jinhwan Sul and Alex Oshin and Evangelos A. Theodorou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01546},
eprint = {2610.01546},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01546},
}
RIS
TY - UNPB
TI - Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming
AU - Jinhwan Sul
AU - Alex Oshin
AU - Evangelos A. Theodorou
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01546
UR - https://arxiv.org/abs/2610.01546
AB - 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× 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×-400× larger than the largest training instances, including Transport LPs with $10.24$ million variables.
ER -