acceptodds
Under review as a conference paper at ICLR 2027

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. Our code is available at https://anonymous.4open.science/r/AHEAD-43D2/.

Primary area:
optimization
Keywords:
Learning to Optimize, Large-Scale Linear Programming, Primal-Dual Methods, Neural Acceleration, Adaptive Stopping

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_6BmiOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proffers a learned neural accelerator for large-scale linear programming (LP) solvers that predicts multiplicative adjustments to primal and dual step sizes. It then uses a learned policy to decide when to hand off to an unmodified solver. The results indicate performance speedups on both synthetic packing and PageRank LP problems.

Critical strengths

First, the paper presents a well-motivated end-to-end objective, where the author's approach designs a lightweight step-size controller that avoids expensive per-variable inference. As such, the author's adaptive handoff policy is a practical and reusable idea.

Second, the author's approach nicely preserves primal-dual hybrid gradient update direction by using solver-native statistics. Sharing parameters across iterations provides interpretability and plausibly supports scale transfer, making it a nice design choice.

Critical weaknesses

Overall, the paper provides a very narrow experimentation scope, as the evaluation is limited to only synthetically generated packing and PageRank LPs. Further, there are no results on standard benchmarks, making the claimed speedups not verified without broader evaluation.

Questions for authors
  1. What are the precise definitions of primal/dual residuals and gap for the general LP form?
  2. Are there any results on heterogeneous, real-world LPs?
7 comments

We thank the reviewer for the thorough review.

W1. We sincerely thank the reviewer for this important concern. We have added two new groups of experiments to evaluate AHEAD on standard LP benchmarks (Section 4.3) and real-world traffic engineering (Section 4.4), highlighted in blue.

Standard benchmarks. On the standard LP benchmark of Gasse et al. [1], AHEAD achieves 3.16–5.95×3.16–5.95\times end-to-end speedups across all eight settings and outperforms PDHG-Net.

Real-world traffic engineering. On the public TEAL benchmark dataset [2], AHEAD transfers zero-shot to three unseen topologies with 2.03–6.24×2.03–6.24\times speedups. It also transfers to a different LP formulation with a 3.71×3.71\times speedup.

These results verify the claimed speedups beyond synthetic LPs. Please see our answer to Q2 below for details.

Q1. For the general LP in Eq. (2), we follow the optimality criteria of PDLP (Applegate et al., 2021, Eq. 6). Let K⊤=(G⊤,A⊤)K^\top = (G^\top, A^\top), q⊤=(h⊤,b⊤)q^\top = (h^\top, b^\top), and y=(yG,yA)y = (y_G, y_A) with yG≥0y_G \ge 0. The PDHG projections maintain x∈[ℓ,u]x \in [\ell,u] and yG≥0y_G \ge 0. Thus, bound violations do not appear separately in rpr_p. The reduced cost is λ=projΛ(c−K⊤y)\lambda = \mathrm{proj}_{\Lambda}(c - K^\top y), where Λ=Λ1×⋯×Λn\Lambda = \Lambda_1 \times \cdots \times \Lambda_n and Λi\Lambda_i is 0\\{0\\}, R+\mathbb{R}^+, R−\mathbb{R}^-, or R\mathbb{R} when xix_i has no finite bound, only a finite lower bound, only a finite upper bound, or both. With λ+=max⁡λ,0\lambda^+ = \max\\{\lambda, 0\\} and λ−=max⁡−λ,0\lambda^- = \max\\{-\lambda, 0\\}, the primal residual, dual residual, and duality gap are

r_p &= \big(Ax - b,\\ (h - Gx)^+\big),\\\\ r_d &= c - K^\top y - \lambda,\\\\ r_g &= \big|c^\top x - (q^\top y + \ell^\top \lambda^+ - u^\top \lambda^-)\big|, \end{aligned}$$ and the corresponding relative errors are $$\begin{aligned} e_p &= \frac{\\|r_p\\|_2}{1 + \\|q\\|_2}, & e_d &= \frac{\\|r_d\\|_2}{1 + \\|c\\|_2},\\\\[5pt] e_g &= \frac{r_g}{ 1 + |c^\top x| + |q^\top y + \ell^\top \lambda^+ - u^\top \lambda^-|}. \end{aligned}$$ An iterate reaches accuracy $\epsilon$ when $\max\\{e_p, e_d, e_g\\} \le \epsilon$. In the special case of Eq. (9), the residuals and gap reduce to $\\|Ax - b\\|_2$, $\\|c - A^\top y\\|_2$, and $|c^\top x - b^\top y|$. We have stated the general form in **Appendix B** of the revision. **Q2.** We sincerely thank the reviewer for this valuable question. We address it with two new groups of heterogeneous LPs: four structurally distinct families from a standard benchmark, and real-world traffic engineering (TE) on real WAN topologies with measured traffic. **Standard LP benchmark.** We evaluate four LP-relaxation families from Gasse et al. [1]: set cover, independent set, facility location and combinatorial auction. We train only on Small instances and test on unseen Small and Large instances, which have 6–10\$\times\$ more variables. AHEAD achieves $3.16–5.95\times$ end-to-end speedups across all eight settings, including $3.16–4.66\times$ on Large instances without retraining. **Traffic engineering.** We use the public TEAL traffic engineering benchmark [2]. B4 uses 36 traffic matrices derived from real measured Abilene traffic and mapped to B4 [3]. ASN98, UsCarrier and Kdl use gravity-model traffic matrices generated following TEAL [2] with held-out seeds for testing. This extends the evaluation to a public application benchmark with measured traffic and multiple network topologies. We train both learned components of AHEAD only on ASN98 maximum-throughput LPs. Without retraining, AHEAD achieves end-to-end speedups over cold-start Gurobi GPU-PDHG of $6.24\times$ on B4, $2.46\times$ on UsCarrier and $2.03\times$ on Kdl. Kdl contains approximately 2.27 million variables compared with 38,000 in ASN98. These results support generalization across topologies and problem sizes. B4 additionally tests transfer to real measured traffic. We also evaluate zero-shot transfer to heterogeneous LPs that change both the network topology and the LP formulation, from ASN98 maximum-throughput LPs to B4 minimum-MLU LPs. These formulations differ in objective, feasible region and constraint structure. AHEAD still achieves a $3.71\times$ end-to-end speedup over cold-start Gurobi GPU-PDHG at the same target accuracy of $10^{-4}$. These experiments are now in **Section 4.3, Section 4.4 and Appendix E** of the revision (in blue). The full setup and results are given below. [1] Gasse et al. *Exact Combinatorial Optimization with Graph Convolutional Neural Networks.* NeurIPS, 2019. [2] Xu et al. *Teal: Learning-Accelerated Optimization of WAN Traffic Engineering.* ACM SIGCOMM, 2023. https://github.com/harvard-cns/teal [3] Jain et al. *B4: Experience with a Globally-Deployed Software Defined WAN.* ACM SIGCOMM, 2013.

To evaluate AHEAD on standard benchmarks and on heterogeneous, real-world LPs, we add experiments on a standard LP benchmark and on real-world traffic engineering (TE).

LP benchmark

We evaluate AHEAD on four LP-relaxation families from the standard LP benchmark of Gasse et al. [1]. We train only on Small instances and test on 100 unseen Small and 100 unseen Large instances per family. Large instances have 6–10$\times$ more variables and are evaluated zero-shot. E2E time includes warm-start computation and Gurobi GPU-PDHG solving to 10−410^{-4}. Speedups are relative to Gurobi's cold start.

Table 1. Runtime on four LP-relaxation benchmarks [1].

InstancesGurobi cold (ms) ↓PDHG-Net E2E (ms) ↓AHEAD E2E (ms) ↓AHEAD speedup ↑
Small set cover28.5631.956.474.41×
Large set cover44.0344.5913.953.16×
Small independent set10.2210.442.534.04×
Large independent set10.7311.022.853.76×
Small facility location35.4770.895.965.95×
Large facility location54.09TL11.604.66×
Small combinatorial auction24.9226.014.665.35×
Large combinatorial auction22.9623.355.144.47×

TL: 60 s time limit.

AHEAD achieves 3.16–5.95× E2E speedups across all eight settings, including 3.16–4.66× on Large instances without retraining.

References

[1] Gasse et al. Exact Combinatorial Optimization with Graph Convolutional Neural Networks. NeurIPS, 2019.

Real-world traffic engineering

TE is a fundamental network optimization problem in production WANs such as Meta's EBB [2] and Google's GGN [3]. It repeatedly solves large-scale LPs as traffic changes, and must handle different network topologies and optimization objectives such as throughput and maximum link utilization (MLU). We evaluate AHEAD on the public TEAL benchmark dataset [1], which contains real-world WAN topologies and measured Abilene traffic. We ask:

  1. Can AHEAD accelerate practical TE LPs across topologies and sizes?
  2. Can it generalize zero-shot across heterogeneous LPs?

Experimental setup

B4 uses 36 measured Abilene traffic matrices mapped to the B4 network topology [4]. For the real ASN98, UsCarrier and Kdl topologies, we generate gravity-model traffic following the TEAL benchmark dataset with held-out test seeds. Each demand has four candidate paths. We consider two LP formulations, maximum throughput and minimum MLU, detailed in Appendix E of the revision. Table 1 lists the problem sizes.

Table 1. Network and LP sizes.

NetworkNodesLinksVariablesConstraintsTest instances
B4123852817036
ASN98981,02438.0K10.5K200
UsCarrier15837899.2K25.2K200
Kdl7541,7902.27M570K50

AHEAD and PDHG-Net train only on ASN98 maximum-throughput LPs. All methods use Gurobi GPU-PDHG at accuracy 10−410^{-4}. End-to-end (E2E) time includes warm-start and remaining solver time per instance. Iterations count solver iterations after handoff. Speedups are over cold-start Gurobi GPU-PDHG.

Generalization across topologies and sizes

Table 2 reports E2E time (ms) / solver iterations. AHEAD trains only on synthetic ASN98 traffic. We test held-out ASN98 instances and transfer zero-shot to B4, UsCarrier and Kdl. Table 2 shows that AHEAD achieves 2.032.03–6.24×6.24\times zero-shot E2E speedups versus at most 1.05×1.05\times for PDHG-Net.

Table 2. Cross-topology generalization on maximum throughput.

MethodASN98B4UsCarrierKdl
Cold start199.1 / 7,85418.67 / 632308.1 / 2,57531,610 / 14,313
PDHG-Net215.0 / 8,33820.61 / 538297.8 / 2,49329,990 / 12,953
AHEAD (K=32K=32)169.2 / 6,60220.68 / 552263.3 / 2,55817,080 / 6,971
AHEAD61.0 / 6852.99 / 54125.0 / 8515,540 / 4,381
AHEAD speedup3.26×6.24×2.46×2.03×

Zero-shot transfer across heterogeneous LPs

We further test zero-shot transfer across both topology and LP formulation. AHEAD and PDHG-Net train on ASN98 maximum-throughput LPs and are tested on 36 B4 minimum-MLU instances without retraining. The two formulations differ in objective, feasible region and constraint structure.

Table 3. Zero-shot transfer across heterogeneous LPs and network topologies.

MethodOpt. gap (%) ↓E2E time (ms) ↓Solver iterations ↓
Cold start—27.621,121
PDHG-Net40.235.581,209
AHEAD (K=32K=32)0.9527.291,039
AHEAD<0.0017.4447

Opt. gap is the mean relative objective error before solver. AHEAD achieves a 3.71×3.71\times E2E speedup over cold start, while PDHG-Net is slower than cold start. These results show that AHEAD also accelerates real-world, heterogeneous LPs.

References

[1] Xu et al. Teal: Learning-Accelerated Optimization of WAN Traffic Engineering. SIGCOMM 2023.

[2] Denis et al. EBB: Reliable and Evolvable Express Backbone Network in Meta. SIGCOMM 2023.

[3] Al-Fares et al. GGN: Experiences in Designing and Deploying Next-Generation Google Global Network. SIGCOMM 2026.

[4] Jain et al. B4: Experience with a Globally-Deployed Software Defined WAN. SIGCOMM 2013.

Reviewer_eN7COpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

AHEAD is a framework for accelerating the a particular numerical solver for linear programs (PDHG). This solver relies on two step size choices per optimization step. AHEAD consists of a first phase of KK accelerated PDHG iterations during which advantageous step sizes are computed, followed by regular PDHG iterations with fixed step sizes. To this end, the authors train two models, one to predict step sizes during the accelerated phase, and a second one to predict the hand-off point at which the accelerated phase ends. These models make their predictions based on a small number hand-crafted features that represent the solver state at a given iteration, allowing the same two predictors to be used across instances and optimization steps. Empirical evaluation on two families of synthetic linear programs show substantial gain of AHEAD over regular PDHG and a competitor acceleration method. Robustness and generalization analysis show that this acceleration consistent across various subgroups of the class of synthetic linear programs tested here.

The core novelty of this paper is the design of the step size and hand-off-time prediction models along with the hand-crafted features they use. This method is relatively simple and versatile, yet achieves significant gains over baselines.

Critical strengths

First, AHEAD optimized for end-to-end solve time instead of other proxies for optimization speed. The model predicting hand-off-time is trained using actual wall-clock time measurements of the the backbone PDHG solver. This allows AHEAD to directly optimize for end-to-end runtime rather than optimization steps or other proxies. This motivation is well aligned with practical considerations.

Second, the hand-crafted solver-state features used by step size and hand-off-time prediction models are principled and based on an understanding of the backbone PDHG solver. These design choices are well justified and credible throughout. The learned policy is therefore grounded in established numerical optimization principles. Moreover, AHEAD is a minimal extension to the backbone PDHG solver, predicting only two step sizes and a hand-off-decision at every iteration. The fact that the method achieves substantial end-to-end acceleration despite this simple setup is a compelling aspect of the method.

Third, the experiments on synthetic linear programs are detailed and include relevant ablations and robustness checks. The advantage over baselines is convincing and robust. The improvements are not limited to a single problem size or a narrowly selected subset of instances within the considered synthetic LP families, which strengthens the conclusions of the paper.

Finally, the paper is very well written and easy to follow. The motivation for the proposed approach is clearly established and the presentation makes it easy to understand both the individual components of AHEAD and how they contribute to the overall acceleration.

Critical weaknesses

The experimental section evaluates AHEAD only on two synthetic task families. No real-word linear programs are included in the analysis. This makes it harder to judge whether advantage of AHEAD would generalize to other task families and real-world linear programs. Given that the method relies on trained predictors for step sizes and hand-off-times, it is not obvious that these predictors would generally be successful in providing strong predictions across a diverse set of real-world problems, even if the training distribution was broader. This substantially limits the evidence for the practical applicability of this method.

Questions for authors

Can you please explain your choice to only evaluate AHEAD on two synthetic task families? Do you expect technical difficulties in extending the approach to a more structurally diverse set of tasks? How would you judge the practical relevance of AHEAD for solving real-world linear programs? My main concern with the paper is that the learned models might work exceptionally well on the controlled, synthetic data distributions on which it is tested here, where all linear programs are structurally similar, and that this might overstate the advantage that AHEAD could achieve in any practical application. I am open to raising my score if the authors can convincingly address this concern, whether through additional experiments or other arguments or evidence.

5 comments

W. We thank the reviewer for the constructive feedback. We have added two new groups of experiments.

First, we evaluate four structurally distinct LP-relaxation families from Gasse et al. [1]. AHEAD achieves 3.16–5.95×3.16–5.95\times end-to-end speedups across all eight settings. It also transfers zero-shot to Large instances with 6–10×6–10\times more variables.

Second, we evaluate real-world traffic engineering on the public TEAL benchmark [2], with measured traffic and real WAN topologies. Trained on one topology and one LP formulation, AHEAD transfers without retraining to unseen topologies, measured traffic, and different LP formulations.

These results show that AHEAD's learned predictors generalize beyond the original task families. We detail them in our answers to the questions below.

Q. We are truly grateful to the reviewer for this thoughtful concern.

Our original evaluation followed the experimental approach of PDHG-Net. Now we have added experiments on the standard LP benchmark of Gasse et al. [1] and on traffic engineering (TE) with the public, real-world TEAL benchmark dataset [2].

AHEAD requires no architectural changes for these tasks. Its predictors read fixed-dimensional solver statistics while its warm-start iterations retain the PDHG update rules. On the four structurally distinct LP-relaxation families [1], AHEAD achieves 3.16–5.95×3.16–5.95\times end-to-end speedups and transfers zero-shot to 6–10×6–10\times larger instances. We train both learned components only on ASN98 maximum-throughput LPs. Without retraining, AHEAD achieves end-to-end speedups over cold-start Gurobi GPU-PDHG of 6.24×6.24\times on B4 and 2.46×2.46\times on UsCarrier and 2.03×2.03\times on Kdl. These results provide evidence of generalization across network topologies and problem sizes. The B4 experiment additionally tests transfer from synthetic training traffic to measured traffic.

We further transfer the same model zero-shot from ASN98 maximum-throughput LPs to B4 minimum-MLU LPs, which changes both the network topology and the LP formulation. Maximum-throughput LPs allow traffic to remain unallocated under fixed link capacities. Minimum-MLU LPs require all traffic to be routed while minimizing maximum link utilization. Demand inequalities become equalities and a global variable couples all link constraints. AHEAD achieves a 3.71×3.71\times end-to-end speedup over cold-start Gurobi GPU-PDHG at the same target accuracy of 10−410^{-4}. These experiments provide evidence of practical acceleration and zero-shot generalization beyond the original synthetic task families. We have added all details and results of these experiments to Sections 4.3 and 4.4 and Appendix E of the revision (in blue). Please see our comment below for the experimental setup and complete results.

[1] Gasse et al. Exact Combinatorial Optimization with Graph Convolutional Neural Networks. NeurIPS, 2019.

[2] Xu et al. Teal: Learning-Accelerated Optimization of WAN Traffic Engineering. ACM SIGCOMM, 2023. https://github.com/harvard-cns/teal

To evaluate AHEAD on standard benchmarks and on heterogeneous, real-world LPs, we add experiments on a standard LP benchmark and on real-world traffic engineering (TE).

LP benchmark

We evaluate AHEAD on four LP-relaxation families from the standard LP benchmark of Gasse et al. [1]. We train only on Small instances and test on 100 unseen Small and 100 unseen Large instances per family. Large instances have 6–10$\times$ more variables and are evaluated zero-shot. E2E time includes warm-start computation and Gurobi GPU-PDHG solving to 10−410^{-4}. Speedups are relative to Gurobi's cold start. AHEAD achieves 3.16–5.95× E2E speedups across all eight settings, including 3.16–4.66× on Large instances without retraining.

Table 1. Runtime on four LP-relaxation benchmarks [1].

InstancesGurobi cold (ms) ↓PDHG-Net E2E (ms) ↓AHEAD E2E (ms) ↓AHEAD speedup ↑
Small set cover28.5631.956.474.41×
Large set cover44.0344.5913.953.16×
Small independent set10.2210.442.534.04×
Large independent set10.7311.022.853.76×
Small facility location35.4770.895.965.95×
Large facility location54.09TL11.604.66×
Small combinatorial auction24.9226.014.665.35×
Large combinatorial auction22.9623.355.144.47×

TL: 60 s time limit.

References

[1] Gasse et al. Exact Combinatorial Optimization with Graph Convolutional Neural Networks. NeurIPS, 2019.

Real-world traffic engineering

TE is a fundamental network optimization problem in production WANs such as Meta's EBB [2] and Google's GGN [3]. It repeatedly solves large-scale LPs as traffic changes, and must handle different network topologies and optimization objectives such as throughput and maximum link utilization (MLU). We evaluate AHEAD on the public TEAL benchmark dataset [1], which contains real-world WAN topologies and measured Abilene traffic. We ask:

  1. Can AHEAD accelerate practical TE LPs across topologies and sizes?
  2. Can it generalize zero-shot across heterogeneous LPs?

Experimental setup

B4 uses 36 measured Abilene traffic matrices mapped to the B4 network topology [4]. For the real ASN98, UsCarrier and Kdl topologies, we generate gravity-model traffic following the TEAL benchmark dataset with held-out test seeds. Each demand has four candidate paths. We consider two LP formulations, maximum throughput and minimum MLU, detailed in Appendix E of the revision. Table 1 lists the problem sizes.

Table 1. Network and LP sizes.

NetworkNodesLinksVariablesConstraintsTest instances
B4123852817036
ASN98981,02438.0K10.5K200
UsCarrier15837899.2K25.2K200
Kdl7541,7902.27M570K50

AHEAD and PDHG-Net train only on ASN98 maximum-throughput LPs. All methods use Gurobi GPU-PDHG at accuracy 10−410^{-4}. End-to-end (E2E) time includes warm-start and remaining solver time per instance. Iterations count solver iterations after handoff. Speedups are over cold-start Gurobi GPU-PDHG.

Generalization across topologies and sizes

Table 2 reports E2E time (ms) / solver iterations. AHEAD trains only on synthetic ASN98 traffic. We test held-out ASN98 instances and transfer zero-shot to B4, UsCarrier and Kdl. Table 2 shows that AHEAD achieves 2.032.03–6.24×6.24\times zero-shot E2E speedups versus at most 1.05×1.05\times for PDHG-Net.

Table 2. Cross-topology generalization on maximum throughput.

MethodASN98B4UsCarrierKdl
Cold start199.1 / 7,85418.67 / 632308.1 / 2,57531,610 / 14,313
PDHG-Net215.0 / 8,33820.61 / 538297.8 / 2,49329,990 / 12,953
AHEAD (K=32K=32)169.2 / 6,60220.68 / 552263.3 / 2,55817,080 / 6,971
AHEAD61.0 / 6852.99 / 54125.0 / 8515,540 / 4,381
AHEAD speedup3.26×6.24×2.46×2.03×

Zero-shot transfer across heterogeneous LPs

We further test zero-shot transfer across both topology and LP formulation. AHEAD and PDHG-Net train on ASN98 maximum-throughput LPs and are tested on 36 B4 minimum-MLU instances without retraining. The two formulations differ in objective, feasible region and constraint structure.

Table 3. Zero-shot transfer across heterogeneous LPs and network topologies.

MethodOpt. gap (%) ↓E2E time (ms) ↓Solver iterations ↓
Cold start—27.621,121
PDHG-Net40.235.581,209
AHEAD (K=32K=32)0.9527.291,039
AHEAD<0.0017.4447

Opt. gap is the mean relative objective error before solver. AHEAD achieves a 3.71×3.71\times E2E speedup over cold start, while PDHG-Net is slower than cold start. These results show that AHEAD also accelerates real-world, heterogeneous LPs.

References

[1] Xu et al. Teal: Learning-Accelerated Optimization of WAN Traffic Engineering. SIGCOMM 2023.

[2] Denis et al. EBB: Reliable and Evolvable Express Backbone Network in Meta. SIGCOMM 2023.

[3] Al-Fares et al. GGN: Experiences in Designing and Deploying Next-Generation Google Global Network. SIGCOMM 2026.

[4] Jain et al. B4: Experience with a Globally-Deployed Software Defined WAN. SIGCOMM 2013.

Reviewer_iFqoOpenReview ↗
Rating
3
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a learning-based accelerator for large-scale linear programming. Experiments on synthetic packing and PageRank LPs demonstrate substantial end-to-end speedups over Gurobi GPU-PDHG, including generalization to larger and shifted problem instances.

Critical strengths
  1. PDHG is popular recently and large scale linear programming is a important problem
  2. The method is clear and easy to read.
  3. The experiment is promising
Critical weaknesses
  1. the contribution is limited compared to PDHG-Net or related work
  2. The method is more like combination from RL methods for L2O and PDHG-Net
  3. neural inference, warm-start iterations 's computation details are missing
Questions for authors

Please compare your work's novelty or method difference with GALLOP: Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming. I just found it came out recently and this paper Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programming

4 comments

Thank you for the insightful comments and questions.

W1. We sincerely thank the reviewer for the comment. PDHG-Net [1] and related unrolled accelerators can reduce solver iterations. However, their inference cost grows with instance size and rollout depth. Their approximate outputs may still require additional solver time to recover feasibility or attain high accuracy. Thus, fewer solver iterations do not guarantee a shorter solve. AHEAD targets end-to-end time: the warm-start time plus the remaining solver time (Eq. 1). Its solution quickly approaches the target accuracy within a short warm-start phase. It also keeps the time spent on each iteration low.

Most existing unrolled accelerators use a fixed number of computational layers and therefore the same compute budget for every instance. They cannot adapt the number of warm-start iterations to each instance and target accuracy. AHEAD recurrently applies a weight-shared step-size predictor to achieve fast convergence with fewer iterations. On unseen network topologies, it cuts solver iterations by up to 96.7% (Table 3 of the revision) and yields 6.5–11.6$\times$ end-to-end speedups on packing LPs (Table 1 of the revision). Weight sharing also allows the warm-start phase to run for any number of iterations. A learned handoff policy adaptively decides whether to hand off to the solver now or continue the warm-start phase. These designs enable end-to-end speedups that PDHG-Net and related unrolled accelerators struggle to achieve.

In the revision (in blue), Section 2 adds comparisons with related learned accelerators. Section 4.3 and 4.4 further show that AHEAD achieves end-to-end speedups on standard LP benchmarks and real-world traffic engineering, where PDHG-Net does not.

W2. We sincerely thank the reviewer for this insightful comment, which helps us clarify the distinct contributions of AHEAD.

AHEAD does not use reinforcement learning. Both learned components are trained with supervised objectives. More importantly, AHEAD is trained for end-to-end acceleration. Fewer solver iterations alone do not fairly measure a neural accelerator, since its own inference also takes time. The handoff policy therefore learns from measured end-to-end solve times, which cover both the warm-start phase and the remaining solver run.

AHEAD also differs fundamentally from PDHG-Net. PDHG-Net is a fixed-depth model whose learned layers predict primal–dual iterates in place of the solver's update. AHEAD instead applies one recurrent step-size layer at every iteration and keeps the solver's update directions. This layer reads compact solver statistics and has very few parameters, so each warm-start iteration stays inexpensive at any scale. It still reduces solver iterations by up to 96.7%. Because the layer is shared across iterations, the warm-start phase can run for any length. The learned handoff then adapts this length to each instance's difficulty and target accuracy, which a fixed-depth model cannot do.

We have clarified both points in Sections 2 and 3.4 of the revision (in blue).

[1] Li et al. PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming. ICML, 2024.

W3. Thank you for the comment. Figure 1 shows the computation flow of each warm-start iteration. First, AHEAD constructs a 10-dimensional solver state by reusing the solver's own intermediate results (Eq. 5). A weight-shared predictor reads this state and predicts two step-size multipliers (Eq. 8). These multipliers rescale the primal and dual step sizes. The primal–dual iterates are then updated using the original PDHG update rules with the adjusted step sizes (Eqs. 3–4). Thus, the shared step-size accelerator operates on solver statistics while the primal–dual update follows the PDHG update rules.

After each update, the learned handoff policy decides whether to hand off to the solver based on the predicted end-to-end times of handing off now or continuing the warm-start phase (Eq. 11). AHEAD hands off when the predicted handoff time is no greater than the predicted continuation time or when KmaxK_{max} is reached. Otherwise, it repeats the warm-start iteration with the same step-size predictor. After handoff, the unmodified solver continues with its own step-size rule and termination criterion. We have made this computation flow clearer in Section 3 of the revision (in blue).

Q1. Thanks for pointing out these recent works. AHEAD differs in the following ways.

Compared with GALLOP (Sul et al., 2026), AHEAD explicitly accounts for the trade-off between warm-start time and remaining solver time. Its handoff policy learns an optimal-stopping point by supervised learning on measured end-to-end solving times. This directly aligns the handoff decision with total solve time. The solver then continues until its termination criterion is met.

Compared with Prasad and Sharma (2026), AHEAD learns state-dependent step-size adjustments rather than tuning solver hyperparameters for an instance distribution. Their tuned hyperparameters stay fixed for every instance in the distribution. AHEAD instead targets generalization beyond the training distribution. To this end, AHEAD adjusts the step sizes at every iteration from the current solver state. Its learned handoff policy then decides, for each instance and target accuracy, when to stop the warm-start phase by comparing predicted end-to-end times. Our experiments demonstrate generalization to unseen problem sizes and distributions. We also evaluate AHEAD across different LP families (Table 2 in revision) and target accuracies (Figure 3).

We have cited both works and clarified these distinctions in Section 2 of the revision .

thanks for your reply, i will keep my score

Thank you for your time and constructive feedback.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.