AHEAD: Adaptive Neural Acceleration for Large-Scale Linear Programming

• Large LPs strain time and memory budgets; first-order methods avoid costly factorizations but often need many iterations, especially at high accuracy.Their progress depends strongly on primal and dual step sizes: conservative choices slow convergence, while aggressive ones can destabilize it.Source: §1 · p. 1
• Existing learned approaches include warm-start prediction, trajectory unrolling, and online parameter feedback, using recurring structure among related instances to reduce subsequent solver cost.These approaches span learned update rules and solver-integrated methods.Source: §1 · p. 1
• Fewer solver iterations do not ensure a shorter end-to-end solve because neural inference and subsequent solver refinement can outweigh the saved time.Fixed-depth unrolled models process every variable and constraint at every layer and use the same compute budget for every instance.Source: §1 · pp. 1–2
• AHEAD uses a weight-shared predictor to adjust primal and dual step sizes, then a learned handoff policy selects the warm-start length for each instance and target accuracy.The predictor reads ten statistics from the solver’s intermediate results; the solver’s update rules remain unchanged.Source: §1 · p. 2
• AHEAD yields many-fold end-to-end speedups across unseen scales, LP families, and accuracy levels by approaching target accuracy in a short warm-start phase.The short phase leaves little remaining solver time.Source: §1 · p. 2
• The predictor reads a 10-dimensional solver-native state and outputs two step-size multipliers, keeping inference time per warm-start iteration small at any problem size.The multipliers steer PDHG through its oscillatory early phase.Source: §1 · p. 2
• AHEAD’s recurrent, weight-shared predictor permits any number of warm-start iterations, while the handoff policy adapts that number to each instance and accuracy.This is designed to reduce end-to-end time.Source: §1 · p. 2

• PDHG uses matrix–vector updates for large-scale saddle-point problems, while PDLP adds preconditioning, adaptive step sizes, primal–dual balancing, and later adaptive restarting.These solvers use hand-designed adaptation rather than learning from related LP solves.Source: §2 · p. 3
• Learned LP components target variable ordering, presolve, projections, simplex bases, and pivot decisions, but their inference overhead may outweigh solver time saved.The passage cites Li et al. (2022), Kuang et al. (2025), Iwata & Sakaue (2025), Fan et al. (2023), Liu et al. (2024), and Lu & Yan (2025).Source: §2 · p. 3
• Prior learned-optimizer work includes LP warm starts and fixed-depth PDHG-Net, while generalization beyond training distributions remains challenging.PDHG-Net predicts primal–dual states and refines them with PDLP; transfer to larger related instances is also reported.Source: §2 · p. 3
• Adaptive-computation research studies input-dependent compute and learned stopping, but LP stopping must account for feasibility, gap signals, and remaining solver work.The paper frames inexpensive LP-iteration control combined with instance-dependent computation as an open question for end-to-end gains across sizes and families.Source: §2 · p. 3

3 AHEAD: LIGHTWEIGHT WARM STARTS WITH ADAPTIVE DEPTH

• AHEAD pairs a weight-shared step-size predictor with a learned policy that selects the warm-start length for each instance and accuracy.The solver then continues from the handoff point until reaching its target accuracy.Source: §3 · p. 3, §3.3 · p. 6

3.1 DESIGN REQUIREMENTS

• The design aims to keep both warm-start runtime and the solver’s remaining time small, since the best handoff point depends on the instance and target accuracy.AHEAD rescales PDHG step sizes while retaining its update directions and valid solver iterates.Source: §3.1 · pp. 3–4

3.2 WEIGHT-SHARED STEP-SIZE PREDICTOR

• A weight-shared predictor reads fixed-dimensional solver-state features and rescales native primal and dual step sizes while preserving PDHG’s update directions.Its state captures feasibility, local stability, primal–dual scaling, and trajectory progress; logarithmic outputs keep the multipliers positive.Source: §3.2 · pp. 4–5

3.3 LEARNED HANDOFF POLICY

• The handoff policy compares predicted end-to-end time for stopping now versus continuing, then hands off when stopping is predicted to be faster.After handoff, the solver resumes with its own step-size rule and termination criterion; this also supports high-accuracy solves.Source: §3.3 · p. 6

3.4 MULTI-HORIZON TRAINING

• Multi-horizon training prepares the predictor to leave useful iterates at candidate handoff points, using distance to the optimum as a proxy for remaining solver work.The handoff policy is trained against measured end-to-end times from solver runs, normalized by cold-start time.Source: §3.4 · pp. 6–7

4.1 EXPERIMENTAL SETTINGS

• The evaluation covers synthetic packing LPs and PageRank LPs, reports end-to-end speedup and iteration reduction at the same target accuracy, and compares cold-start, learned, and AHEAD variants.The default target accuracy is ϵ = 10^-4; the Gurobi GPU-PDHG comparison includes PDHG-Net and a validation-selected fixed warm-start horizon.Source: §4.1 · p. 7, §4.2 · p. 7

4.2 ACCELERATION

• AHEAD generalizes across packing-LP scales and distributions, while adaptive handoff nearly matches the per-instance best horizon and outperforms fixed handoff across difficulty tiers.The evaluation also reports speedups across target accuracies while keeping the same solver termination criterion.Source: §4.2 · p. 8, §4.3 · p. 9

4.3 GENERALIZATION

• Without handoff, AHEAD reaches the target primal-residual tolerance; adaptive handoff reaches it earlier than AHEAD without handoff or cold-start PDHG.PDHG-Net remains above the target in the reported comparison.Source: §4.3 · p. 8, Figure 4 · p. 8
• Adaptive handoff comes close to the per-instance optimal horizon, and acceleration persists across evaluated target accuracies under the same PDLP termination criterion.The fixed-horizon comparison uses K = 32, while the per-instance optimum is the horizon with the shortest end-to-end time.Source: §4.3 · pp. 8–9
• AHEAD achieves approximately 9×, 11×, and 12× speedup on easy, medium, and hard instances, respectively, versus roughly 3×, 5×, and 8× for fixed K = 32.The instances are grouped by cold-start Gurobi PDHG runtimes; OR-Tools PDLP and PDHG-Net remain below the cold Gurobi baseline in this comparison.Source: §4.3 · p. 9

4.4 ABLATION

• Adding solver-state features reduces total steps from 104.4 to 76.8, a 26.4% reduction relative to the fixed step-size baseline.Movement and nonlinearity provide the largest incremental improvement; the feature groups represent complementary information for step-size prediction.Source: §4.4 · p. 9, Table 2 · p. 9
• Parameter sharing across controller iterations requires 67.8 total steps and 35.8 continuation steps, outperforming the tested larger controllers.Increasing the controller from five layers of width 64 to seven layers of width 128 raises total steps from 68.5 to 72.9.Source: §4.4 · p. 9

5 CONCLUSION

• AHEAD achieves many-fold end-to-end speedups on packing and PageRank LPs across unseen scales, difficulty levels, and target accuracies.The conclusion identifies extending AHEAD to real-world LPs and other first-order solvers as future work.Source: §5 · p. 9
• AHEAD predicts step sizes while retaining the solver’s update directions, keeping each warm-start iteration inexpensive and each iterate a valid warm start.The predictor adjusts primal and dual step sizes rather than predicting the solution.Source: §5 · p. 9
• A weight-shared predictor runs recurrently, allowing the warm-start phase to last any number of iterations.A learned handoff policy selects that number for each instance and accuracy.Source: §5 · p. 9
• Future work will extend AHEAD to real-world LPs and other first-order solvers.Source: §5 · p. 9

A ENGINEERING ACCELERATIONS IN PDLP

• PDLP adjusts step magnitude and primal–dual scaling using local stability checks, rejecting and shrinking candidate steps that violate the check.This allows larger steps along locally stable trajectory portions than choices based only on the global operator norm.Source: A ENGINEERING ACCELERATIONS IN PDLP · p. 13
• Adaptive restarting retains weighted averaging when useful, but restarts when gap decay, stalled progress, or excessive inner-loop length warrants it.The mechanism discards accumulated trajectory history when it ceases to improve the normalized duality gap.Source: A ENGINEERING ACCELERATIONS IN PDLP · p. 13
• At restart points, PDLP updates the primal weight to approximately balance weighted primal and dual distances without abrupt changes.The three mechanisms address step magnitude, trajectory history, and primal–dual balance, respectively.Source: A ENGINEERING ACCELERATIONS IN PDLP · p. 13

B TRAINING

• Training uses a dataset with target solutions (x*, y*) and candidate horizons {8, 16, 32, 64, 128}.Source: B TRAINING · p. 14
• Each training step samples a mini-batch and one shared horizon K from the candidate set.Source: B TRAINING · p. 14

C.1 PAGERANK

• The resulting LP has one equality row 1^T x = 1 and n inequality rows, matching the paper’s LP form with S = 1.Source: §C.1 · p. 14
• PageRank instances use Barabási–Albert graphs with attachment degree 3 and damping factor λ = 0.85.The LP has one equality row 1^T x = 1 and n inequality rows.Source: §C.1 · p. 14
• Using 1^T x = 1, the formulation retains equivalent sparse constraints instead of directly constructing a dense teleportation matrix.Source: §C.1 · p. 14

C.2 SYNTHETIC PACKING LPS

• The synthetic instances follow the packing form s.t. 1^T x = S, Ax ≤ b, x ≥ 0.Source: §C.2 · p. 14
• Instances have n ∈ [10^5, 10^6] variables and m = 0.1n inequalities, with about 100 variables per inequality and objective coefficients sampled uniformly from −1 to 2.The matrix entries are generated from Bernoulli masks and uniform values in [0.5, 1.0].Source: §C.2 · pp. 14–15
• The construction makes x0 feasible and controls difficulty through slack: larger slack yields mostly inactive inequalities, while smaller slack yields more binding constraints at the optimum.Source: §C.2 · p. 15
• Training and in-distribution tests use n ∈ [10^5, 10^6], while the size-shift tests use 20 larger instances and distribution-shift tests use 20 instances with changed generation parameters.For the difficulty study, 60 held-out instances are split into Easy, Medium, and Hard groups by cold-start time.Source: §C.2 · p. 15

C.3 EXPERIMENTAL ENVIRONMENT AND MEASUREMENT PROTOCOL

• All experiments were conducted on the same machine, and Table 4 summarizes the hardware and software environment.Source: §C.3 · p. 15, Table 4 · p. 15
• Aggregate end-to-end time is defined as T_i = T_warm + T_solver.Source: §C.3 · p. 15
• After K complete PDHG updates, AHEAD passes the current primal and dual iterates to the solver, which continues with its own update rule; warm-start time is included in end-to-end time.No predictor state or step size is transferred.Source: §C.3 · p. 15