WorksComputer Science
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 variables, AHEAD achieves – 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.
Introduction
Linear programming (LP) underpins large-scale decision-making, but instances with millions of variables and constraints strain time and memory budgets [9, 31]. First-order methods (FOMs) are attractive at this scale because they rely on sparse matrix-vector multiplications rather than costly factorizations [25, 3, 29]. However, they often need many iterations, particularly at high accuracy [3]. Their progress depends strongly on primal and dual step sizes: conservative choices slow convergence, while aggressive ones can destabilize it [13, 30].
Learning-to-optimize (L2O) offers a promising way to reduce the computational cost of iterative optimization. Early learned optimizers replace hand-designed update rules with learned dynamics [23, 1, 37]. More recent solver-integrated methods predict one-shot warm starts [34, 11], unroll first-order or interior-point trajectories [22, 33, 15, 17], or learn feedback policies that tune algorithmic parameters online [32]. Across these approaches, learning exploits recurring structure among related instances to reduce the cost subsequently performed by an optimization solver.
Fewer solver iterations, however, do not guarantee a shorter solve. In learned acceleration of LP solvers, a solve typically has two stages: a neural accelerator first produces a warm start, and the classical solver then continues from it until the solution reaches the target accuracy. We call the two stages together, the neural warm start followed by the classical solve, end-to-end neural acceleration. Existing unrolled accelerators typically rely on a fixed number of computational layers. Each learned layer processes every variable and constraint and predicts new primal–dual iterates in place of the solver’s native update, causing inference cost to grow with both instance size and rollout depth [33, 22]. These approximate outputs may still require additional solver running time to recover feasibility or attain high accuracy [34, 12]. Moreover, fixed-depth models use the same compute budget for every instance. This prevents them from adapting computational efforts to instance-specific needs and limits generalization across problem distributions and difficulty levels [7, 36]. Consequently, neural inference and subsequent refinement can offset or even outweigh the time saved by reducing solver iterations. These limitations lead to our central question: What neural accelerator design achieves end-to-end speedups on large-scale LPs across sizes and target accuracies?
To address this question, we introduce AHEAD (Adaptive Horizon for End-to-end Acceleration of Primal–Dual Solvers), a lightweight neural accelerator for first-order LP solvers. In the first stage, which we call the warm-start phase, AHEAD applies a weight-shared step-size predictor at every iteration and accelerates the solver only by adjusting its step sizes. To keep each warm-start iteration cheap, the predictor reads only ten statistics built from the solver’s own intermediate results and outputs one multiplier for each of the primal and dual step sizes. AHEAD’s solution quickly approaches the target accuracy on its own. Because only the step sizes change, AHEAD is also fully aligned with the solver: when high accuracy is required, its solution can be handed directly to the solver as a warm start. A learned handoff policy picks this moment by predicting whether stopping now or continuing gives a shorter end-to-end time. Together, these designs address three core challenges: they let the solver reach the target accuracy in fewer iterations, keep the time spent on each iteration low, and adapt the number of warm-start iterations to each instance and accuracy.
Our main contributions are summarized as follows:
End-to-end speedups from fast convergence. AHEAD’s solution quickly approaches the target accuracy within a short warm-start phase, leaving little remaining solver time, which yields many-fold end-to-end speedups across unseen scales, LP families, and accuracy levels.
Low time per iteration. We keep the inference time of each warm-start iteration small at any problem size: the predictor reads a 10-dimensional solver-native state and outputs two step-size multipliers, which suffice to steer PDHG through its oscillatory early phase.
Adaptive number of warm-start iterations. We apply a weight-shared predictor at each iteration recurrently, so the warm-start phase can run for any number of iterations, and a learned handoff policy selects this number for each instance and accuracy, further reducing the end-to-end time.
Related Work
First-order methods for large-scale linear programming. Chambolle & Pock [6] introduced PDHG, whose matrix–vector updates suit large-scale saddle-point problems. Applegate et al. [2] developed PDLP, preconditioning, adaptive step sizes, and primal–dual balancing; subsequent work used adaptive restarting to improve high-accuracy convergence [3]. These solvers adapt through hand-designed rules, but do not learn from related LP solves.
Learning components of LP solvers. Li et al. [24] learn variable reorderings, while Kuang et al. [21] learn presolve routines, including when to stop presolving. Iwata & Sakaue [20] generate instance-specific projections to reduce LP dimension. Other works learns simplex bases or pivot decisions (Fan et al., 2023; Liu et al., 2024; Lu & Yan, 2025). These methods can accelerate stages such as presolve or simplex search, but their neural inference overhead may outweigh the solver time saved.
Learned optimizers and warm starts. Learned update rules can transfer across optimization tasks [1, 37], although generalization outside the training distribution remains challenging [26]. Sambharya et al. [34] learn warm starts for quadratic optimization. For LPs, Li et al. (2024) use a fixed-depth PDHG-Net to predict primal–dual states, then refine them with PDLP; they also demonstrate transfer to larger instances of related problem families. Oshin et al. [32] learn dimension-agnostic parameter feedback for QP and SQP solvers.
Adaptive computation. Graves [14]; Banino et al. [5]; Hou et al. [18] study input-dependent neural computation, while Chen et al. [8] learn when to stop the neural network. For LPs, however, stopping decisions should exploit LP-specific feasibility and gap signals and account for the remaining solver work after learned computation ends. Taken together, prior work leaves open how to combine inexpensive control of LP iterations with instance-dependent computation to obtain consistent end-to-end gains across problem sizes and families.
AHEAD: Lightweight Warm Starts with Adaptive Depth
For an LP instance , consider a learned accelerator parameterized by that controls the solver during a warm-start phase of iterations, and then hands the solver a primal–dual warm start ; we call this step the handoff. The solver continues from until it reaches the target accuracy . We define the end-to-end time of instance is
where the warm-start time covers the warm-start iterations, including the inference of the predictor and the handoff policy, and the remaining solver time covers the solver’s run from the warm start until it reaches . The cold-start time covers the same run from the solver’s default initial point.
AHEAD yields an end-to-end speedup on instance if , where is the number of warm-start iterations selected for instance . Our goal is to achieve this on all or most instances, so we design AHEAD to keep both terms of (1) small. Section 3.1 derives what each term requires of the accelerator. Based on this analysis, AHEAD consists of two learned components: a weight-shared step-size predictor (Section 3.2) that adjusts the primal and dual step sizes during the warm-start phase, and a learned handoff policy (Section 3.3) that selects the number of warm-start iterations for each instance and accuracy. Section 3.4 describes how we train the predictor over varying numbers of warm-start iterations, and Figure 1 summarizes the framework.
Figure 1. Framework of AHEAD.
Design Requirements
Reducing requires keeping both terms of (1) small. To make warm-starting worthwhile, its runtime must stay small: the accelerator runs each warm-start iteration, so its input must be cheap to compute and fixed-dimensional regardless of problem size. We consider LPs in bounded form
where the bounds and may contain infinite entries. PDHG ([6]) is a classical first-order method for Equation (2). Let , , and for the inequality and equality rows, with . PDHG alternates
where . PDHG-based solvers such as PDLP first go through an oscillatory exploration phase and only then converge toward a solution (Applegate et al. [3]). This observation motivates a lightweight step-size predictor that adjusts and at every iteration to shorten this early phase. After warm-start iterations, the accelerator hands the warm start to the solver, which continues until it reaches . The best number of warm-start iterations balances the two terms and depends on both the instance and . However, is known only in hindsight, since evaluating it requires running solver to termination from the warm start at every candidate . A practical accelerator therefore needs an online rule that selects .
Formally, AHEAD keeps Equation (3) and only rescales its step sizes:
where are the solver’s own step sizes and are learned step-size multipliers. AHEAD thus makes two online decisions: it predicts at every warm-start iteration and selects for each instance and . The predictor outputs only two scalars per iteration, and the iterate at every warm-start iteration remains a valid PDHG iterate.
Weight-Shared Step-Size Predictor
To predict at each warm-start iteration, we design a weight-shared step-size predictor (Figure 1, left). It maps the current solver state to the two multipliers and shares its weights across iterations. We first describe the state and then the predictor.
Solver state. At each warm-start iteration , the predictor reads a state that describes the current progress of PDHG. To choose the step sizes for the next iteration, the state must answer four questions: how much the current iterate violates the primal and dual constraints, whether a larger step would remain stable, how to split the step between primal and dual, and whether recent steps make progress or oscillate. PDLP (Applegate et al. [4]) already answers each question with its own mechanism: its termination residuals, its step-acceptance check, its primal weight, and its restart rule (Appendix § 6). We therefore build one group of features from each mechanism, reusing only the solver’s own intermediate results, so that is cheap to compute and has the same dimension for every LP, as required in § 3.1:
Feasibility. A primal--dual pair of an LP is optimal if and only if is primal feasible, is dual feasible, and the duality gap is zero. The first group tracks the two feasibility conditions: the primal residual measures how much violates the primal constraints, and the dual residual measures how much violates the dual constraints. Large residuals indicate an early phase of the solve, where larger steps pay off, and small residuals call for finer steps.
Local stability. The second group tells the predictor whether a larger step would remain stable. With constant step size, PDHG converges when (Chambolle & Pock [6]). This bound is often too conservative in practice. PDLP (Applegate et al. [2]) instead adapts the step size with a local stability condition on the actual movement: it computes the update in Equation (3) with a trial step size, keeps the update if the condition holds, and otherwise shrinks the step size and recomputes the update (Appendix § 6). Let and denote the change between the last two iterations, and write and , where sets the overall step size and is the solver’s primal weight. With the weighted movement and the primal–dual interaction , PDLP’s condition can be written as
This condition always holds when . When , it limits the step size to . We define the utilization as the ratio of the current step size to this upper limit, , so the condition holds exactly when . We therefore include , , , and the bounded ratio in the state: tells the predictor how close the current step size is to this limit, and the sign of tells it whether the condition can be violated at all. The predictor thus observes the same condition that the classical solver imposes on each update, and can set the next multipliers.
Primal–dual scaling. The third group tells the predictor how to split the step between primal and dual. The solver sets this split through its primal weight: and . The best pair of multipliers thus depend on , so we include the detrended log-weight , which treats reciprocal primal and dual scalings symmetrically.
Local trajectory. The last group tells the predictor whether recent steps make progress or oscillate. PDHG iterates often spiral around saddle points before settling, which slows early progress [6, 3]. PDLP counters this with restarts triggered by the normalized duality gap, which measures how far an iterate is from the saddle point but needs an extra optimization problem to compute, so PDLP evaluates it only periodically [2]. However, our predictor needs this information at every iteration, and computing the gap that often would be too expensive. We therefore measure the directional consistency of consecutive updates with cosine similarities, which are inexpensive to compute at every iteration:
where the small constant prevents division by zero. Up to , each cosine equals when consecutive updates point in the same direction and when they reverse, and it does not change when either update is rescaled, for example by a new step size. Values near thus indicate steady progress and suggest that a larger step is safe, whereas values near indicate oscillation and need to adapt the step smaller. We also include the movement ratio with , which shows whether the updates are growing () or shrinking (). These features give the predictor the progress information that PDLP’s restart rule relies on. Thus, AHEAD itself never restarts during the warm-start phase.
Weight-shared step-size predictor. Given , the predictor outputs the logarithms of the two step-size multipliers,
where is a small MLP with tanh activations. Predicting logarithms keeps both multipliers positive, and (4) applies them to the solver’s native step sizes.
The primal–dual update directions of the solver are faithfully kept in AHEAD, as we find them to be efficient and reliable directions towards optimality. The primal and dual step sizes are much harder to tune, since first-order methods like PDLP lack the higher-order information as interior-point methods to find the optimal step size for each update. Hand-designed rules either overestimate or underestimate the optimal step size. Learning the optimal step sizes only can thus reap the most benefit of learning without introducing more model complexity that lowers per-iteration efficiency.
Another core design principle is a looped architecture for recursive solution refinement: we apply the same predictor at every warm-start iteration. This is a paradigm shift from existing neural solvers with a fixed model depth and independent model parameters per-layer: they require more parameters and cannot adapt to the varying number of iterations. AHEAD runs like a classical solver: it recursively refines primal–dual solutions, without a pre-determined number of iterations, until the handoff policy ends the warm-start phase. This adaptive recursion is key to generalizability across instances with different sizes and difficulties, as reported in other literature such as Chen et al., [8] and recurrent networks Schwarzschild et al., [35].
Learned Handoff Policy
With the weight-shared predictor, AHEAD can run for any number of warm-start iterations. For moderate accuracy requirements, such as , the warm-start iterations alone already bring the solution close to the accuracy. Because AHEAD is fully aligned with the solver, it enables a second capability: when higher accuracy is required, AHEAD hands its solution directly to the solver as warm start. This warm start substantially reduces the number of iterations the solver needs to converge at high accuracy, while still achieving a large end-to-end speedup over a cold start.
A key question in this handoff is when to stop the warm-start phase and switch to the solver’s own iterations. Switching too late wastes warm-start iterations that no longer reduce the remaining solver time, whereas switching too early gives the solver a weaker warm start than AHEAD could provide. We address this with a learned handoff policy (Figure 1, right). It selects the number of warm start iterations for any given target accuracy . Since the best choice is known only in hindsight (§ 3.1), the policy makes this decision online. At every warm-start iteration , it reads a handoff state , predicts the end-to-end time of stopping now and of continuing, and ends the warm-start phase once stopping is predicted to be faster. Unlike halting in adaptive neural computation ([14, 5]), this decision depends on the remaining solver time after handoff, not on the quality of a network output.
Handoff state. Whether to handoff depends on how close the solver is to convergence and how fast it is approaching it. The solver monitors the primal residual, dual residual, and duality gap,
and reaches target accuracy when ([2]). Convergence is decided by the slowest criterion, and the same residual may be close enough for a loose but far from a tight one. We therefore measure, for each criterion, the log-gap to the target accuracy
where avoids . Because is considered in the handoff state, the same learned handoff policy can adapt the number of warm-start iterations across target accuracies.
Handoff rule. At warm-start iteration , AHEAD can either hand off now or continue. An MLP maps the handoff state to
where and estimate the end-to-end time of handing off now and of handing off at the best later iteration, respectively. Both are divided by the cold-start time, so they are comparable across instances of different sizes and difficulty. AHEAD hands off at the first warm-start iteration with , or after iterations if this condition never holds. estimate the same quantity, so the rule needs no extra threshold. After the handoff, the solver continues from the warm start with its own step-size rule and termination criterion, so every returned solution meets the target accuracy , exactly as a cold-start solve does.
Multi-Horizon Training
To serve different accuracy requirements, we train the predictor over varying horizons rather than a fixed one. The handoff policy may end learned acceleration at any checkpoint, so the predictor must leave a useful iterate at every candidate horizon. Formally, let be the set of candidate horizons and an optimal primal–dual solution of instance . We train the predictor by
where is the handoff iterate after learned iterations. The normalized distance to the optimum serves as a differentiable proxy for the remaining solver work . This objective can be viewed as training over a distribution of horizons rather than a single fixed depth. By sampling , the predictor learns a state-dependent rule that remains useful for any horizon the handoff policy may pick, and the shared weights let it run for horizons outside . We initialize the output layer of at zero, so that and training starts from the solver’s native step-size rule.
Training the handoff policy. Unlike the distance used to train the predictor, the end-to-end time is measured in wall-clock and is not differentiable. We therefore freeze the trained predictor, roll it out on each training instance, and measure at every warm-start iteration the end-to-end time of handing off at , divided by the cold-start time, , using actual solver runs from the warm start rather than a surrogate. The regression targets for the two predictions of the handoff policy are
the normalized end-to-end time of handing off now and the best one attainable by handing off later. We fit by
where is the set of training instances for the handoff policy and is the set of warm-start iterations evaluated on instance . Because both outputs are regressed onto the same normalized end-to-end time, the handoff rule compares them directly, without a hand-tuned threshold.
Experiments
In this section, we first examine the proposed adaptive accelerator against common baselines, and further examine the generalization capabilities, adaptive stopping and difficulty. Finally, we conduct ablation analysis to analyze the underlying structure of AHEAD.
Experimental Settings
Datasets and metrics. We evaluate on two LP families: synthetic packing LPs with nonnegative variables, one equality constraint, and about sparse inequalities, and PageRank LPs on Barabási–Albert graphs [2, 19]. Both follow the LP form in § 3.1. We report the end-to-end speedup, whose wall-clock time includes AHEAD’s inference, presolve, and solver execution, and the reduction in iterations, both at the same target accuracy ( by default). Test instances are disjoint from the training instances. Appendices § 8.§ 1, § 8.§ 2, and § 8.§ 3 give the generation details and the measurement protocol.
Baselines and Evaluation. We compare against three groups of baselines. Cold-start solvers form the first group: Gurobi GPU PDHG (PDHGGPU=1) and OR-Tools PDLP. The second group is the learned baseline PDHG-Net [22], the closest learned method to ours. The third group contains two variants of AHEAD: a fixed horizon selected on validation, and a per-instance optimal that marks the best achievable handoff.
Training Details. The candidate horizons are . We train the predictor for 200 epochs with Adam, a learning rate of , cosine annealing, and a batch size of 8. Each mini-batch shares one sampled horizon , which enables batched rollouts and still gives an unbiased estimate of (12). We clip gradients so that pathological primal or dual errors do not dominate an update. The handoff policy is then trained on the frozen predictor’s trajectories.
Acceleration
Table 1 compares AHEAD with PDHG-Net and with a fixed number of warm-start iterations selected on validation, all on the Gurobi GPU-PDHG backbone at .
The test sets contain 50 held-out packing LPs, 20 larger packing LPs with , and 20 packing LPs from an unseen distribution. (1) AHEAD generalizes across scale and distribution. Its predictor only rescales step sizes from a fixed-dimensional solver state and never predicts the solution, unlike PDHG-Net, whose predictions are tied to the training distribution. (2) Adaptive handoff nearly matches the best handoff. The best number of warm-start iterations varies across instances, so a fixed number wastes iterations or stops too early, whereas the handoff policy stops once further iterations no longer save time. (3) The advantage grows with problem size. Larger PageRank LPs require more iterations, and the weight-shared predictor adapts to each instance, whereas PDHG-Net has fixed depth (Figure 2).
Figure 2. Speedup on PageRank LPs.
| Method | IID () | Size shift () | Unseen distribution () | |||
| 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 () | 5.63× | 3.2 | 5.09× | 1.1 | 3.25× | 0.99 |
| PDHG-Net ([22]) | 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 | 12.36× | 1.5 | 12.75× | 0.42 | 7.06× | 0.46 |
Table 1. Acceleration with the Gurobi PDHG backbone on packing-type LPs.
Generalization

Figure 3a. Fixed vs. adaptive handoff.

Figure 3b. Robustness across target acc.

Figure 3c. Speedup across difficulty tiers.
Does AHEAD rely on solver continuation? We disable handoff on a representative LP instance and compare AHEAD’s residual trajectory with adaptive AHEAD, cold-start PDHG, and PDHG-Net. Figure 4 supports two observations. (1) AHEAD can reach the target tolerance without native continuation. When AHEAD runs without handoff, it reduces the primal residual and reaches the target, whereas PDHG-Net remains above it. (2) Learned acceleration and solver refinement are complementary. Adaptive handoff reaches the target earlier than AHEAD without handoff or the cold-start solver, indicating that AHEAD accelerates early trajectory while the native solver completes the refinement. Handoff improves efficiency rather than providing progress that AHEAD cannot achieve on its own.
Figure 4. Primal-residual trajectories without early solver handoff.
Adaptive Stopping. To evaluate whether AHEAD can select an effective number of warm-start iterations, we compare adaptive handoff with a fixed and the per-instance optimal , the with the shortest end-to-end time on each instance; we also evaluate robustness across target accuracies. The figures support two observations. (1) Adaptive handoff comes close to the per-instance optimal . In Figure 3(a), the adaptive speedup distribution shifts markedly beyond the fixed-horizon baseline and toward the oracle, showing that the current solver state provides useful information for selecting an instance-specific handoff point. (2) Acceleration persists across target accuracies. Figure 3(b) shows consistently large runtime reductions across all evaluated tolerances. Because every run must satisfy the same PDLP termination criterion, these gains demonstrate consistent speedups for convergence without relaxing final solution accuracy.

Figure 3. Robustness across acceleration horizons, target accuracies, and problem difficulty levels.
Difficulty. To test whether acceleration persists as instances become harder, we generate 60 packing-LP test instances unseen during training and divide them into three equal-sized groups, Easy, Medium, and Hard, based on their cold-start Gurobi PDHG runtimes. We then split them into three equal-sized groups: the shortest third as Easy, the middle third as Medium, and the longest third as Hard. Figure 3(c) reports AHEAD achieves approximately , , and speedup on easy, medium, and hard instances, respectively. The corresponding fixed results are roughly , , and . Adaptive handoff improves speedup in every tier, while OR-Tools PDLP and PDHG-Net remain below the cold Gurobi baseline in this comparison.
Ablation
Which solver-state features matter? Table 2 incrementally introduces the four groups of solver-state features. Adding the primal and dual residuals reduces the total number of steps from 104.4 to 92.5. Movement and nonlinearity provide the largest incremental improvement, further reducing the total to 80.4 steps. Incorporating the primal weight and cosine features subsequently reduces the total to 79.3 and 76.8, respectively. Overall, the complete representation achieves a 26.4% reduction relative to the fixed step-size baseline. These results indicate that feasibility, local stability, primal-dual scaling, and trajectory geometry provide complementary information for step-size prediction.
| Input state | Total steps | (%) |
| Fixed stepsize | 104.4 | – |
| + Residuals | 92.5 | 11.4 |
| + Movement/nonlinearity | 80.4 | 13.1 |
| + Primal weight | 79.3 | 1.4 |
| + Cosine geometry (AHEAD) | 76.8 | 3.2 |
Table 2. Incremental ablation of solver-state features. Features are added cumulatively.
Does the improvement come from model capacity? Table 3 compares controller architectures while fixing the solver-state representation and training objective. Increasing the controller from five layers with width 64 to seven layers with width 128 increases the total number of steps from 68.5 to 72.9. The improvement therefore cannot be explained simply by increased network capacity. In contrast, sharing controller parameters across iterations produces the best result, requiring 67.8 total steps and 35.8 continuation steps. This supports matching the controller parameterization to the iteration-invariant update structure of the underlying optimizer.
| Controller | Total steps | Continuation steps |
| 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.
Conclusion
We asked what neural accelerator design achieves end-to-end speedups on large-scale LPs across sizes and target accuracies. AHEAD answers with three design choices. First, it learns only the step sizes and keeps the solver’s update directions, so each warm-start iteration stays inexpensive and every iterate remains a valid warm start. Second, its weight-shared predictor runs recurrently, so the warm-start phase can last any number of iterations. Third, a learned handoff policy selects this number for each instance and accuracy. Together, these choices let the solver reach the target accuracy in fewer iterations with little time per iteration, yielding many-fold end-to-end speedups on packing and PageRank LPs across unseen scales, difficulty levels, and target accuracies. Future work will extend AHEAD to real-world LPs and other first-order solvers.
Engineering Accelerations in PDLP
Classical PDHG uses fixed primal and dual step sizes chosen according to a global stability condition, making its convergence highly sensitive to conservative step-size selection and mismatched primal–dual scaling. Beyond presolving and diagonal preconditioning, PDLP accelerates conventional PDHG through three coupled mechanisms: adaptive step-size selection, adaptive restarting, and dynamic primal weighting.
First, PDHG parameterizes its primal and dual step sizes as
where controls the overall step magnitude and controls the relative primal-dual scaling. Conventional PDHG selects according to the global condition , which guarantees convergence but is often overly conservative. PDLP instead evaluates each candidate step using the local condition , where and . The next candidate step size is updated as . A candidate violating the local condition is rejected and recomputed using a smaller step. Because depends on the realized primal-dual movement rather than only on the global operator norm, PDLP can take substantially larger steps along locally stable portions of the trajectory.
The second mechanism controls trajectory history through adaptive restarting. Within outer iteration , PDLP maintains a step-size-weighted average of the inner iterates, . Progress is evaluated using the normalized duality gap
and .
At each restart check, PDLP selects between the current iterate and its weighted average:
The outer loop is restarted when the normalized duality gap exhibits sufficient decay, when local progress stalls after necessary decay has been achieved, or when the inner loop becomes excessively long. This mechanism retains averaging when it is beneficial but discards accumulated trajectory history once it ceases to improve the normalized gap.
Finally, PDLP updates the primal weight only at restart points. Let , . The new primal weight is obtained through log-space smoothing: , where PDLP uses . This update approximately balances the weighted primal and dual distances while avoiding abrupt changes that may destabilize PDHG. Consequently, the three mechanisms address distinct limitations of conventional PDHG: adaptive step sizes control the step magnitude using local stability, restarts manage accumulated trajectory history, and the primal weight balances progress between the primal and dual spaces.
Training
Algorithm 1 Random-Horizon Training
Require: Dataset with targets ; ; batch size
Initialization
repeat
Sample a mini-batch and a shared
for all do
end for
Update using
until convergence
Dataset
PageRank
Following Applegate et al. [2], we generate PageRank LPs with the formulation of Iouditski & Nesterov [19], using a damping factor . The resulting LP has one equality row and inequality rows, and matches the LP form in § 3.1 with and the transition constraints written as sparse linear inequalities.
For each instance, we first sample a Barabási–Albert preferential-attachment graph with attachment degree 3. Let denote its column-normalized adjacency matrix, such that is column stochastic. Given a damping factor , the PageRank transition matrix is
The corresponding PageRank vector can be obtained as a feasible solution to
Directly constructing would introduce a dense teleportation matrix. Using the normalization constraint , we instead retain the equivalent sparse constraints
Synthetic Packing LPs
We construct a family of synthetic packing LPs of the form
Each instance has variables and inequality constraints. The constraint matrix is generated as
with density , so each inequality involves about 100 variables on average. The variables have no explicit upper bounds, and the instances match the LP form in § 3.1 directly. The objective coefficients are sampled as .
For each instance, we first sample the equality right-hand side as . We then draw
such that and . The inequality right-hand side is constructed as
where the entries of are sampled independently. This construction makes feasible and controls instance difficulty through the magnitude of the available slack: larger slack values produce mostly inactive inequalities, whereas smaller values yield a larger fraction of binding constraints at the optimum.
Data splits. The training instances and the in-distribution test set are drawn from the generator above with . The size-shift test set contains 20 instances with from the same generator. The distribution-shift test set contains 20 instances whose generation parameters differ from those used for training. The difficulty tiers in Figure 3(c) group 60 held-out instances by their cold-start time. Training, validation, and test instances are generated using disjoint random seeds and checked for duplicate content. For the difficulty study (Figure 3(c)), we sort all test instances by their cold-start time on Gurobi PDHG and split them into three equal-sized groups: the shortest third as Easy, the middle third as Medium, and the longest third as Hard.
Experimental Environment and Measurement Protocol
All experiments were conducted on the same machine. Table 4 summarizes the hardware and software environment.
| Component | Configuration |
| GPU | NVIDIA A100 PCIe 40GB; driver 580.173.02 |
| CPU | 2× 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 |
| CUDA toolkit | 12.0 (V12.0.140) |
| OR-Tools | 9.15.6755 |
| Gurobi | 13.0.3, GPU-enabled build |
Table 4. Experimental environment.
Timing metric. Unless stated otherwise, the aggregate end-to-end speedup is
where is the end-to-end time defined in § 3.
Warm-start iterations and handoff. The number of warm-start iterations counts complete PDHG updates whose step-size multipliers are predicted by AHEAD. After iterations, AHEAD passes the current primal iterate and dual iterate to the solver as its initial primal and dual solution; for Gurobi, these are assigned through PStart and DStart. No predictor state or step size is transferred, and the solver continues with its own update rule. The warm-start iterations are included in the end-to-end time. The fixed number of warm-start iterations used as a baseline is selected on validation data.
References
- [1]Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W. Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando de Freitas. Learning to learn by gradient descent by gradient descent. In Advances in Neural Information Processing Systems, volume 29, pp. 3981–3989, 2016. URL https://arxiv.org/abs/1606.04474.
- [2]David Applegate, Mateo Díaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O’Donoghue, and Warren Schudy. Practical large-scale linear programming using primal-dual hybrid gradient. In Advances in Neural Information Processing Systems, volume 34, pp. 20243–20257, 2021.arxiv.org/abs/2106.04756
- [3]David Applegate, Oliver Hinder, Haihao Lu, and Miles Lubin. Faster first-order primal-dual methods for linear programming using restarts and sharpness. Mathematical Programming, 201(1–2): 133–184, 2023. doi: 10.1007/s10107-022-01901-9. URL https://doi.org/10.1007/s10107-022-01901-9.
- [4]David Applegate, Mateo Díaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O’Donoghue, and Warren Schudy. PDLP: A practical first-order method for large-scale linear programming. Mathematical Programming Computation, 2026. doi: 10.1007/s12532-026-00309-2. URL https://doi.org/10.1007/s12532-026-00309-2.
- [5]Andrea Banino, Jan Balaguer, and Charles Blundell. PonderNet: Learning to ponder. arXiv preprint arXiv:2107.05407, 2021. doi: 10.48550/arXiv.2107.05407. URL https://arxiv.org/abs/2107.05407. Presented at the 8th ICML Workshop on Automated Machine Learning.
- [6]Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision, 40(1):120–145, 2011.DOI
- [7]Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. Learning to optimize: A primer and a benchmark. Journal of Machine Learning Research, 23(189):1–59, 2022. URL https://jmlr.org/papers/v23/21-0308.html.arxiv.org/abs/2103.12828
- [8]Xinshi Chen, Hanjun Dai, Yu Li, Xin Gao, and Le Song. Learning to stop while learning to predict. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 1520–1530. PMLR, 2020. URL https://proceedings.mlr.press/v119/chen20c.html.arxiv.org/abs/2006.05082
- [9]George B. Dantzig. Linear Programming and Extensions. Princeton University Press, 1963.
- [11]Weizhi Gao, Zichao Hou, Han Xu, and Xiaorui Liu. Certified robustness for deep equilibrium models via serialized random smoothing. Advances in Neural Information Processing Systems, 37:1370–1401, 2024a.arxiv.org/abs/2411.00899
- [12]Xi Gao, Jinxin Xiong, Akang Wang, Qihong Duan, Jiang Xue, and Qingjiang Shi. IPM-LSTM: A learning-based interior point method for solving nonlinear programs. In Advances in Neural Information Processing Systems, volume 37, pp. 122891–122916, 2024b. URL https://proceedings.neurips.cc/paper_files/paper/2024/hash/de0da9c42ee713f2cea eed7bc40c522d-Abstract-Conference.html.arxiv.org/abs/2410.15731
- [13]Tom Goldstein, Min Li, Xiaoming Yuan, Ernie Esser, and Richard Baraniuk. Adaptive primal-dual hybrid gradient methods for saddle-point problems. arXiv preprint arXiv:1305.0546, 2013.arxiv.org/abs/1305.0546
- [14]Alex Graves. Adaptive computation time for recurrent neural networks. arXiv preprint arXiv:1603.08983, 2016. doi: 10.48550/arXiv.1603.08983. URL https://arxiv.org/abs/1603.08983.
- [15]Zichao Hou, Ruiqi Feng, Tyler Derr, and Xiaorui Liu. Robust graph neural networks via unbiased aggregation. Advances in Neural Information Processing Systems, 37:110097–110130, 2024a.arxiv.org/abs/2311.14934
- [17]Zhichao Hou, MohamadAli Torkamani, Hamid Krim, and Xiaorui Liu. Robustness reprogramming for representation learning. In International Conference on Learning Representations, volume 2025, pp. 53682–53704, 2025.arxiv.org/abs/2410.04577
- [18]Zhichao Hou, Weizhi Gao, and Xiaorui Liu. Fine-grained iterative adversarial attacks with limited computation budget. In International Conference on Learning Representations, volume 2026, pp. 75235–75250, 2026.arxiv.org/abs/2510.26981
- [19]Anatoli Iouditski and Yuri Nesterov. Primal-dual subgradient methods for minimizing uniformly convex functions, 2014. URL https://arxiv.org/abs/1401.1792.
- [20]Tomoharu Iwata and Shinsaku Sakaue. Learning to generate projections for reducing dimensionality of heterogeneous linear programming problems. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 26627–26641. PMLR, 2025.
- [21]Yufei Kuang, Xijun Li, Jie Wang, Fangzhou Zhu, Meng Lu, Zhihai Wang, Jia Zeng, Houqiang Li, Yongdong Zhang, and Feng Wu. Accelerate presolve in large-scale linear programming via reinforcement learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 47 (8):6660–6672, 2025. doi: 10.1109/TPAMI.2025.3562286. URL https://doi.org/10.1109/TPAMI.2025.3562286.
- [22]Bingheng Li, Linxin Yang, Yupeng Chen, Semmiao Wang, Haitao Mao, Qian Chen, Yao Ma, Akang Wang, Tian Dong, Jiliang Tang, and Ruoyu Sun. PDHG-unrolled learning-to-optimize method for large-scale linear programming. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 29164–29180. PMLR, 2024. URL https://proceedings.mlr.press/v235/li24ce.html.arxiv.org/abs/2406.01908
- [23]Ke Li and Jitendra Malik. Learning to optimize. arXiv preprint arXiv:1606.01885, 2016. doi: 10.48550/arXiv.1606.01885. URL https://arxiv.org/abs/1606.01885.
- [24]Xijun Li, Qingyu Qu, Fangzhou Zhu, Jia Zeng, Mingxuan Yuan, Kun Mao, and Jie Wang. Learning to reformulate for linear programming. arXiv preprint arXiv:2201.06216, 2022. doi: 10.48550/arXiv.2201.06216. URL https://arxiv.org/abs/2201.06216.
- [25]Tianyi Lin, Shiqian Ma, Yinyu Ye, and Shuzhong Zhang. An ADMM-based interior-point method for large-scale linear programming. Optimization Methods and Software, 36(2–3):389–424, 2021. doi: 10.1080/10556788.2020.1821200.DOI
- [26]Jialin Liu, Xiaohan Chen, Zhangyang Wang, Wotao Yin, and Hanqin Cai. Towards constituting mathematical structures for learning to optimize. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 21426–21449. PMLR, 2023. URL https://proceedings.mlr.press/v202/liu23e.html.arxiv.org/abs/2305.18577
- [29]Haihao Lu and Jinwen Yang. cuPDLP.jl: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia. Operations Research, 73(6):3440–3452, 2025. doi: 10.1287/opre.2024.1069. URL https://doi.org/10.1287/opre.2024.1069.
- [30]Yura Malitsky and Thomas Pock. A first-order primal-dual algorithm with linesearch. SIAM Journal on Optimization, 28(1):411–432, 2018. doi: 10.1137/16M1092015. URL https://doi.org/10.1137/16M1092015.
- [31]Yurii Nesterov. Subgradient methods for huge-scale optimization problems. Mathematical Programming, 146(1–2):275–297, 2014. doi: 10.1007/s10107-013-0686-4.DOI
- [32]Alex Oshin, Rahul Ghosh, Augustinos Saravanos, and Evangelos Theodorou. Deep FlexQP: Accelerated nonlinear programming via deep unfolding. In International Conference on Learning Representations, 2026. URL https://proceedings.iclr.cc/paper_files/paper/2026/hash/84cd19dedba8b8b7461d86c246f2c372-Abstract-Conference.html.arxiv.org/abs/2512.01565
- [33]Chendi Qian, Didier Chételat, and Christopher Morris. Exploring the power of graph neural networks in solving linear optimization problems. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 1432–1440. PMLR, 2024. URL https://proceedings.mlr.press/v238/qian24a.html.arxiv.org/abs/2310.10603
- [34]Rajiv Sambharya, Georgina Hall, Brandon Amos, and Bartolomeo Stellato. Learning to warm-start fixed-point optimization algorithms. Journal of Machine Learning Research, 25(166):1–46, 2024. URL https://jmlr.org/papers/v25/23-1174.html.arxiv.org/abs/2309.07835
- [35]Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Furong Huang, Uzi Vishkin, Micah Goldblum, and Tom Goldstein. Can you learn an algorithm? generalizing from easy to hard problems with recurrent networks, 2021. URL https://arxiv.org/abs/2106.04537.
- [36]Michael Sucker and Peter Ochs. A generalization result for convergence in learning-to-optimize. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 57212–57230. PMLR, 2025.arxiv.org/abs/2410.07704
- [37]Olga Wichrowska, Niru Maheswaranathan, Matthew W. Hoffman, Sergio Gómez Colmenarejo, Misha Denil, Nando de Freitas, and Jascha Sohl-Dickstein. Learned optimizers that scale and generalize. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 3751–3760. PMLR, 2017. URL https://proceedings.mlr.press/v70/wichrowska17a.html.arxiv.org/abs/1703.04813


