Large-scale linear programs with millions of variables and constraints strain time and memory budgets. First-order methods such as the primal-dual hybrid gradient scale to this regime because they avoid matrix factorizations, but they require many iterations. Learned accelerators can reduce these iterations, yet fewer iterations do not guarantee a shorter solve. Learning inference also takes time, and running the accelerator longer trades solver time for inference time. Existing unrolled accelerators handle this trade-off poorly: each layer processes every variable and constraint, the predicted iterates still need solver refinement, and every instance runs the same layers. We therefore ask: What neural accelerator design achieves end-to-end speedups on large-scale linear programs across sizes and target accuracies? We introduce AHEAD, an accelerator that predicts step sizes for first-order linear programming solvers while keeping their update rules. Its weight-shared predictor reads compact solver statistics and rescales the primal and dual step sizes, so each warm-start iteration stays inexpensive and a short warm-start phase hands the solver a warm start. A learned handoff policy sets the number of warm-start iterations for each instance and target accuracy, after which the solver finishes under its own termination criterion. On packing linear programs with up to 107 variables, AHEAD achieves 6.5--11.6× end-to-end speedups over Gurobi's first-order solver from a cold start, including on instances of unseen sizes and distributions. The gains extend to PageRank linear programs and hold across difficulty levels and target accuracies.
Figures & tables
Figure 1: Framework of AHEAD.
Figure 2: Speedup on PageRank LPs.
Method
IID ( n=50 )
Size shift ( n=20 )
Unseen distribution ( n=20 )
Speedup
Time (s)
Speedup
Time (s)
Speedup
Time (s)
Cold PDHG (Gurobi)
1.00×
18.2
1.00×
5.3
1.00×
3.2
Best validation K ( K=32 )
5.63×
3.2
5.09×
1.1
3.25×
0.99
PDHG-Net ( Li et al., 2024 )
1.23×
14.8
1.18×
4.5
1.06×
3.1
AHEAD
11.07×
1.6
11.59×
0.46
6.48×
0.50
Per-instance optimal K⋆
12.36×
1.5
12.75×
0.42
7.06×
0.46
Table 1: Acceleration with the Gurobi PDHG backbone on packing-type LPs.
Figure 3: Robustness across acceleration horizons, target accuracies, and problem difficulty levels.
Figure 4: Primal-residual trajectories without early solver handoff.
Input state
Total steps ↓
Δ (%) ↑
Fixed stepsize
104.4
–
+ Residuals
92.5
11.4
+ Movement/nonlinearity
80.4
13.1
+ Primal weight ωk
79.3
1.4
+ Cosine geometry (AHEAD)
76.8
3.2
Table 2: Incremental ablation of solver-state features. Features are added cumulatively.
The Linear Assignment Problem is a fundamental combinatorial optimization task where classical exact solvers ensure optimality but suffer from an O(N3) bottleneck, while recent neural approximations struggle with scalability and exactness. We propose a learning-augmented framework that accelerates exact solvers by predicting dual variables to warm-start the search, backed by a fallback mechanism to preserve worst-case guarantees. Central to our approach is RowDualNet, a lightweight, row-independent architecture that avoids the O(N2) memory bottleneck of graph models, enabling scalable neural warm-starting up to N=16,384. Feasibility is guaranteed by construction via the Min-Trick mechanism, completely eliminating the need for costly iterative projections. Empirically, our method drastically reduces the search effort of the Jonker-Volgenant (LAPJV) algorithm, yielding robust zero-shot generalization with strict optimality and end-to-end speedups of over 2x on complex synthetic data, 1.25x on real-world tracking, and 1.5x on transportation networks.
Ilay Yavlovich, Jad Agbaria, Muhamed Mhamed +2
Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology, Haifa, Israel.
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.
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.