AHEAD: Adaptive Neural Acceleration for Large-Scale Linear Programming

Sihao Liu; Zhichao Hou; Huayue Gu; Raiyan Rahman; Liang Wu; Ruozhou Yu; Xiaorui Liu

cs.LGOct 26, 2026

AHEAD: Adaptive Neural Acceleration for Large-Scale Linear Programming

Authors: Sihao Liu, Zhichao Hou, Huayue Gu, Raiyan Rahman, Liang Wu, Ruozhou Yu, Xiaorui Liu

Organizations: North Carolina State University · Kennesaw State University · Nokia Applied Research

Abstract

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 $10^7$ variables, AHEAD achieves $6.5$ -- $11.6\times$ 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 2: Speedup on PageRank LPs.

Method	IID ( $n{=}50$ )		Size shift ( $n{=}20$ )		Unseen distribution ( $n{=}20$ )
Method	Speedup	Time (s)	Speedup	Time (s)	Speedup	Time (s)
Cold PDHG (Gurobi)	$1.00\times$	$18.2$	$1.00\times$	$5.3$	$1.00\times$	$3.2$
Best validation $K$ ( $K{=}32$ )	$5.63\times$	$3.2$	$5.09\times$	$1.1$	$3.25\times$	$0.99$
PDHG-Net ( Li et al., 2024 )	$1.23\times$	$14.8$	$1.18\times$	$4.5$	$1.06\times$	$3.1$
AHEAD	$\mathbf{11.07\times}$	$\mathbf{1.6}$	$\mathbf{11.59\times}$	$\mathbf{0.46}$	$\mathbf{6.48\times}$	$\mathbf{0.50}$
Per-instance optimal $K^{\star}$	$12.36\times$	$1.5$	$12.75\times$	$0.42$	$7.06\times$	$0.46$

Table 1: Acceleration with the Gurobi PDHG backbone on packing-type LPs.

Panel of Figure 3 — 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 $\downarrow$	$\bm{\Delta}$ (%) $\uparrow$
Fixed stepsize	104.4	–
$+$ Residuals	92.5	11.4
$+$ Movement/nonlinearity	80.4	13.1
$+$ Primal weight $\omega_{k}$	79.3	1.4
$+$ Cosine geometry (AHEAD)	76.8	3.2

Table 2: Incremental ablation of solver-state features. Features are added cumulatively.

Controller	Total steps $\downarrow$	Continuation steps $\downarrow$
5 layers, width 64	68.5	36.5
7 layers, width 128	72.9	40.9
Weight-shared (AHEAD)	67.8	35.8

Table 3: Predictor-architecture ablation.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Component	Configuration
GPU	NVIDIA A100 PCIe 40GB; driver 580.173.02
CPU	2 $\times$ Intel Xeon Gold 5317; 24 cores, 48 threads
Memory	251 GiB
OS	Ubuntu 24.04.3 LTS; Linux 6.8.0-139
Python	3.12.9
PyTorch	2.9.0

Appendix

Table 4: Experimental environment.

Learning to Optimize

Learning to Optimize uses data to adapt algorithms, solver decisions, and solution maps for faster or better optimization.

See all 138 papers

Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts
May 10, 2026Ilay Yavlovich, Jad Agbaria, Muhamed Mhamed +2Neural Network Optimization Combinatorial Optimization
Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology, Haifa, Israel.
Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming
Oct 1, 2026Jinhwan Sul, Alex Oshin, Evangelos A. TheodorouPrimal-Dual Optimization Reinforcement Learning
Georgia Institute of Technology, USA
Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programming
Jun 7, 2026Siddharth Prasad, Dravyansh SharmaPrimal-Dual Optimization Constrained Optimization
Toyota Technological Institute at Chicago

May 10, 2026J/K move · Enter open · S save

Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts

Ilay Yavlovich, Jad Agbaria, Muhamed Mhamed, Nir Weinberger+1

Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology, Haifa, Israel.

Neural Network Optimization Combinatorial Optimization Learning-Augmented Algorithms

Open paper AskPDF arXiv

The Linear Assignment Problem is a fundamental combinatorial optimization task where classical exact solvers ensure optimality but suffer from an

\mathcal{O}(N^{3})

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

\mathcal{O}(N^{2})

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.

Abstract

Learning to Optimize

Explore similar work

Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts

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

Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programming