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

arXiv: https://arxiv.org/abs/2610.01546 · HTML: https://mlsanity.com/paper/2610.01546/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 38 of its 51 references that are in the map.
- First posted on arXiv 1 Oct 2026.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 30 of 38)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Algorithm Unrolling: Interpretable, Efficient Deep Learning for Signal and Image Processing](https://mlsanity.com/paper/1912.10557/) (2019)
- [Learning to Optimize: A Primer and A Benchmark](https://mlsanity.com/paper/2103.12828/) (2021)
- [OSQP: An Operator Splitting Solver for Quadratic Programs](https://mlsanity.com/paper/1711.08013/) (2017)
- [Understanding and correcting pathologies in the training of learned optimizers](https://mlsanity.com/paper/1810.10180/) (2018)
- [Tutorial on amortized optimization](https://mlsanity.com/paper/2202.00665/) (2022)
- [Deep Unfolding: Model-Based Inspiration of Novel Deep Architectures](https://mlsanity.com/paper/1409.2574/) (2014)
- [Parametrized Deep Q-Networks Learning: Reinforcement Learning with Discrete-Continuous Hybrid Action Space](https://mlsanity.com/paper/1810.06394/) (2018)
- [Hybrid Actor-Critic Reinforcement Learning in Parameterized Action Space](https://mlsanity.com/paper/1903.01344/) (2019)
- [Discrete and Continuous Action Representation for Practical RL in Video Games](https://mlsanity.com/paper/1912.11077/) (2019)
- [Tuning-free Plug-and-Play Proximal Algorithm for Inverse Imaging Problems](https://mlsanity.com/paper/2002.09611/) (2020)
- [Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient](https://mlsanity.com/paper/2106.04756/) (2021)
- [Accelerating Quadratic Optimization with Reinforcement Learning](https://mlsanity.com/paper/2107.10847/) (2021)
- [Multi-Pass Q-Networks for Deep Reinforcement Learning with Parameterised Action Spaces](https://mlsanity.com/paper/1905.04388/) (2019)
- [Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems](https://mlsanity.com/paper/2310.10603/) (2023)
- [PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming](https://mlsanity.com/paper/2406.01908/) (2024)
- [Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness](https://mlsanity.com/paper/2105.12715/) (2021)
- [Dimension-Wise Importance Sampling Weight Clipping for Sample-Efficient Reinforcement Learning](https://mlsanity.com/paper/1905.02363/) (2019)
- [Deep Distributed Optimization for Large-Scale Quadratic Programming](https://mlsanity.com/paper/2412.12156/) (2024)
- [Neural Fixed-Point Acceleration for Convex Optimization](https://mlsanity.com/paper/2107.10254/) (2021)
- [Learning to Pivot as a Smart Expert](https://mlsanity.com/paper/2308.08171/) (2023)
- [cuPDLP.jl: A GPU Implementation of Restarted Primal-Dual Hybrid Gradient for Linear Programming in Julia](https://mlsanity.com/paper/2311.12180/) (2023)
- [Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learning](https://mlsanity.com/paper/2310.11845/) (2023)
- [cuPDLP-C: A Strengthened Implementation of cuPDLP for Linear Programming by C language](https://mlsanity.com/paper/2312.14832/) (2023)
- [Learning Algorithm Hyperparameters for Fast Parametric Convex Optimization](https://mlsanity.com/paper/2411.15717/) (2024)
- [MPAX: Mathematical Programming in JAX](https://mlsanity.com/paper/2412.09734/) (2024)
- [Learning-to-Optimize with PAC-Bayesian Guarantees: Theoretical Considerations and Practical Implementation](https://mlsanity.com/paper/2404.03290/) (2024)
- [Data-Driven Performance Guarantees for Classical and Learned Optimizers](https://mlsanity.com/paper/2404.13831/) (2024)

## Abstract (arXiv)

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.