Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming
Primal-dual hybrid gradient methods can solve large linear programs on GPUs, but their speed depends on delicately coordinated step sizes, restarts, and acceleration heuristics. GALLOP replaces these hand-tuned rules with a reinforcement learning policy that jointly picks continuous parameters and discrete restart decisions inside a generalized PDHG update. The approach is notable because the learned policy is dimension-agnostic and reportedly generalizes from small training instances to LPs hundreds of times larger without retraining.
GALLOP is a carefully engineered RL-based learning-to-optimize framework that demonstrates strong empirical acceleration of PDHG for linear programming. By unifying extrapolation, history correction, and restart anchoring in a single parameterized update and introducing a groupwise PPO objective for hybrid actions, the paper makes a solid algorithmic contribution. However, global convergence of the learned policy is not guaranteed, and the results are benchmarked primarily against MPAX and an internal hand-tuned baseline rather than a broader suite of industrial or first-order solvers.
The dimension-agnostic policy design is the strongest element: observations and controls are independent of problem dimension, enabling zero-shot transfer from small training instances to LPs up to $400\times$ larger within the same family. The GA-PDHG update is also theoretically appealing, subsuming Halpern, reflected Halpern, Anderson, and Krasnosel'skii--Mann iterations as special cases via a shared coefficientization that RL can explore.
The paper does not establish global convergence for the learned controller; Proposition 3.1 only applies when both $\{\hat z_t\}$ and $\{z_t\}$ converge, and the authors explicitly caution that they do not handle arbitrary learned control sequences. The RL reward depends on the merit $M^{\mathrm{rel}}$ and tunable hyperparameters $\chi$ and $T_{\max}$, whose sensitivity and robustness outside the tested LP families are not characterized.\nFurthermore, generalization experiments are confined to within-family scaling and one public benchmark, and the authors acknowledge that available GPU memory capped the largest instances they could evaluate.
Ablations support the claim that every learned control group contributes, with the learned step size providing the largest marginal gain (iterations jump from 165 to 457 when replaced). Iteration-count and wall-clock reductions over MPAX are large and consistent across all six families. That said, the solver comparisons are relatively narrow: MPAX and an in-house hand-tuned baseline are the principal competitors, and the comparison to PDLP on the public item-placement benchmark uses a looser relative tolerance of $10^{-4}$ versus GALLOP's stricter criterion.
The authors document hyperparameters, network architectures, and action transformations in Appendix F, which aids reproduction, but no public code repository or data archive is referenced in the available text. Independent reproduction would therefore require rebuilding the custom JAX solver and the groupwise PPO training loop. The reported algorithm wall-clock time also excludes JIT compilation and preconditioning, so end-to-end runtime may differ from the headline speedups.
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.