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

Jinhwan Sul; Alex Oshin; Evangelos A. Theodorou

math.OCOct 1, 2026

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

Authors: Jinhwan Sul, Alex Oshin, Evangelos A. Theodorou

Organizations: Georgia Institute of Technology, USA

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.

Figures & tables

Figure 1: Conceptual comparison of (a) vanilla PDHG, (b) PDHG with heuristic acceleration and restarts, and (c) GALLOP with learned solver parameters and restarts.

Figure 2: Feedback control loop for GA-PDHG. Red symbols denote control variables selected by the policy network from solver observations.

Problem class	$\beta$	$e$
Transport	3.79	0.35
Auction	8.99	0.94
Random LPs	2.01	0.13

Table 2: Clipping ratio (%).

Family	Density	$m/n$
Random LP	$1.28\%$	$0.5$
Transport	$0.625\%$	$0.0125$
Auction	$0.313\%$	$0.25$
Min-cost flow	$0.0417\%$	$0.167$
Robust inventory	$0.326\%$	$0.341$
$L_{\infty}$ regression	$100\%$	$26.7$

Table 3: Density

\operatorname{nnz}\left(A\right)/(mn)

and

m/n

at each family’s largest training size.

Panel of Figure 3 — Figure 3: Convergence on one unseen LP per family at the largest training size. Labels mark the first iteration meeting tolerance $10^{-6}$ (dashed line).

Family	$(m,n)$	Size ratio	Ours	HT	MPAX	Ours	HT	MPAX	Ours	HT	MPAX
			Iterations			Matrix–vector products			Algorithm wall clock (ms)
Random LP	(10,000, 20,000)	$1\times$	284	440	664	570	883	1,384	110	140	408
	(30,000, 60,000)	$3\times$	280	421	663	561	844	1,384	151	199	1,175
	(150,000, 300,000)	$15\times$	290	428	702	582	859	1,468	450	626	7,202
Transport	(320, 25,600)	$1\times$	164	633	548	329	1,268	1,150	39	107	87
	(1,600, 640,000)	$25\times$	153	533	536	308	1,068	1,128	102	286	308

Table 4: Test results (four-LP medians). The “Size ratio” column reports the ratio of test size to each family’s largest training size. Size is measured in

n

except for robust inventory (item count

N

) and

L_{\infty}

regression (

m

at fixed

n=9

). Ours denotes GALLOP , HT denotes GA-PDHG (HT).

Figure 4: Size generalization (four-LP medians). Shading marks the largest training size.

Solver	Iterations
GALLOP	186.7
MPAX	1,089.0
PDHG-Net + PDLP	422
PDLP	550.4

Table 5: IP-S. Mean iteration counts.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Paper / solver	Step size	Primal weight	Restarting criteria	Acceleration method
PDLP ( Applegate et al., 2021 )	Adaptive	EMA	Normalized duality gap	Averaging
raPDHG ( Applegate et al., 2023 )	Constant	Constant	Normalized duality gap	Averaging
cuPDLP-C ( Lu et al., 2023 )	Adaptive	EMA	KKT error	Averaging
cuPDLP.jl ( Lu & Yang, 2025 )	Adaptive	EMA	KKT error	Averaging
rHPDHG / r 2 HPDHG ( Lu & Yang, 2024 )	Adaptive	EMA	Fixed-point residual	Halpern / Reflected Halpern
MPAX (LP) ( Lu et al., 2024 )	Adaptive	EMA	Fixed-point residual	Reflected Halpern

Appendix

Table 7: Representative PDHG-based LP solver papers and their enhancement techniques.

Family	Multiplier	$m$	$n$	$\operatorname{nnz}(A)$	LPs per split
					Train / Held-out	Compared
Transport	0.125 $\times$	120	3,200	6,400	64 / –	–
	0.25 $\times$	160	6,400	12,800	64 / 16	4
	0.5 $\times$	240	12,800	25,600	64 / –	–
	1 $\times$	320	25,600	51,200	32 / 16	4
	2.5 $\times$	506	64,000	128,000	– / 8	4

Appendix

Table 8: Training, validation, and test sizes for transport, auction, and min-cost flow.

Family	Multiplier	$m$	$n$	$\operatorname{nnz}(A)$	LPs per split
					Train / Held-out	Compared
Robust inventory	0.25 $\times$	390	1,101	5,376	64 / –	4
	0.5 $\times$	760	2,201	10,751	128 / 4	4
	1 $\times$	1,500	4,401	21,501	64 / 4	4
	1.5 $\times$	2,240	6,601	32,251	– / 4	4
	2 $\times$	2,980	8,801	43,001	– / 2	4

Appendix

Table 9: Training, validation, and test sizes for inventory,

L_{\infty}

regression, and random LP.

Family	$(m,n)$	Ours	HT	MPAX	Ours	HT	MPAX	Ours	HT	MPAX
		Iterations to $\epsilon_{\mathrm{tol}}$			Matrix–vector products			Algorithm wall clock (ms)
Transport	(160, 6,400)	146	488	550	294	979	1,158	46	119	76
	(320, 25,600) †	164	633	548	329	1,268	1,150	39	107	87
	(506, 64,000)	155	674	540	312	1,349	1,134	46	143	96
	(720, 128,000)	150	628	526	302	1,257	1,108	48	146	122
	(1,012, 256,000)	140	554	518	282	1,111	1,090	52	154	156

Appendix

Table 10: Full test results for transport, auction, and min-cost flow (four-LP medians).

		Iterations to $\epsilon_{\mathrm{tol}}$			Matrix–vector products			Algorithm wall clock (ms)
Family	$(m,n)$	Ours	HT	MPAX	Ours	HT	MPAX	Ours	HT	MPAX
Robust inventory	(390, 1,101)	1,426	2,892	3,774	2,853	5,787	7,682	259	397	309
	(760, 2,201)	1,250	4,242	3,072	2,503	8,485	6,256	260	659	482
	(1,500, 4,401) †	1,905	4,266	3,875	3,812	8,535	7,872	507	915	432
	(2,240, 6,601)	2,140	10,294	5,888	4,282	20,591	11,934	635	2,529	591
	(2,980, 8,801)	2,311	7,768	5,348	4,624	15,537	10,854	570	1,494	661

Appendix

Table 11: Full test results for inventory,

L_{\infty}

regression, and random LP (four-LP medians).

Family	Learning rate	PPO minibatch	$c_{V}$	$\lambda_{\mathrm{prior}}$	$L_{\omega}$
Transport	$5\times 10^{-4}$	16,384	0.5	0.02	4.6
Auction	$5\times 10^{-4}$	4,096	0.5	0	2.0
Min-cost flow	$10^{-4}$	16,384	0.5	0.02	4.6
Robust inventory	$10^{-4}$	16,384	0.5	0.05	4.6
$L_{\infty}$ regression	$5\times 10^{-4}$	16,384	0.2	0.01	4.6
Random LP	$10^{-4}$	16,384	0.5	0.02	4.6

Appendix

Table 12: Settings of the training runs used in the six-family comparison.

Family	Initial standard deviations	Minimum standard deviations
Transport	$\left(0.3,0.2,0.4,0.4,0.2\right)$	$\left(0.2,0.1,0.2,0.2,0.1\right)$
Auction	$\left(0.4,0.2,0.4,0.6,0.2\right)$	$\left(0.001,0.001,0.001,0.12,0.001\right)$
Min-cost flow	$\left(0.2,0.3,0.3,0.4,0.2\right)$	$\left(0.05,0.2,0.05,0.05,0.05\right)$
Robust inventory	$\left(0.05,0.05,0.07,0.1,0.07\right)$	$\left(0.01,0.01,0.01,0.02,0.02\right)$
$L_{\infty}$ regression	$\left(0.4,0.2,0.4,0.5,0.2\right)$	$\left(0.2,0.1,0.05,0.3,0.1\right)$
Random LP	$\left(0.1,0.1,0.1,0.1,0.1\right)$	$\left(0.02,0.01,0.02,0.02,0.01\right)$

Appendix

Table 13: Gaussian exploration settings. Both tuples use the order

\left(\alpha,\beta,\zeta,\eta,\omega\right)

; the common upper bound is

1.5

Explore similar work

Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programming
Jun 7, 2026Siddharth Prasad, Dravyansh SharmaLinear Programming Primal-Dual Methods
Toyota Technological Institute at Chicago
Learned Preconditioning for a Primal-Dual Interior-Point Method
Sep 28, 2026Abhinav Madabhushi, Jialin Liu, Minxin ZhangPrimal-Dual Methods Spectral Preconditioning
Department of Mathematics, University of California, Los Angeles · School of Data, Mathematical, and Statistical Sciences, University of Central Florida
Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving
Sep 23, 2026Jiameng LyuLinear Programming Learning-Augmented Algorithms
Department of Management Science, School of Management, Fudan University, Shanghai 200433, China

Jun 7, 2026, math.OCJ/K move · Enter open · S save

Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programming

Siddharth Prasad, Dravyansh Sharma

Toyota Technological Institute at Chicago

Linear Programming Primal-Dual Methods Tuning Optimal Sample Complexity

Open paper AskPDF arXiv

Recent research has developed practical, parallelizable first-order methods for large scale linear programming, but performance is highly dependent on hyperparameter selection. We derive generalization guarantees for hyperparameter tuning within (cu)PDLP, a state-of-the-art first-order LP solver designed for modern hardware. First, we pin down the behavior of PDHG, the primal-dual hybrid gradient algorithm that underlies PDLP, as a function of its step size and primal weight, leading to linear sample complexity guarantees for learning those parameters. We then conduct a structural analysis of PDLP, which augments PDHG with several specialized techniques like preconditioning, adaptive step sizes, averaging, adaptive restarts, and smoothed primal weight updates. Our analysis captures the behavior of the solution trajectory as a function of the hyperparameters and leverages recent advances in data-driven algorithm design to obtain polynomial sample complexity guarantees for learning those hyperparameters. Finally, we conduct proof-of-concept experiments that demonstrate the need for data-driven PDLP parameter tuning. Our results showcase the versatility of the data-driven algorithm design toolkit for principled hyperparameter tuning within solver-grade implementations of complex modern optimization algorithms.

Abstract

Explore similar work

Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programming

Learned Preconditioning for a Primal-Dual Interior-Point Method

Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving