AHEAD: Adaptive Neural Acceleration for Large-Scale Linear Programming
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 107 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.
Related
- Direct Neural Dynamic Programming Adaptive Control of Knee and Ankle Joints in a Simulated Prosthetic Leg Model
- Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving
- PDLP: a practical first-order method for large-scale linear programming
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Subgraph Isomorphism, Integer Linear Programming, and Lattices: A Linear Algebraic Framework
BibTeX
@misc{liu2026ahead,
title = {{AHEAD: Adaptive Neural Acceleration for Large-Scale Linear Programming}},
author = {Sihao Liu and Zhichao Hou and Huayue Gu and Raiyan Rahman and Liang Wu and Ruozhou Yu and Xiaorui Liu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.36321},
eprint = {2610.36321},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.36321},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - AHEAD: Adaptive Neural Acceleration for Large-Scale Linear Programming
AU - Sihao Liu
AU - Zhichao Hou
AU - Huayue Gu
AU - Raiyan Rahman
AU - Liang Wu
AU - Ruozhou Yu
AU - Xiaorui Liu
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.36321
UR - https://arxiv.org/abs/2610.36321
AB - 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.
ER -