- 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
- What are the precise definitions of primal/dual residuals and gap for the general LP form?
- Are there any results on heterogeneous, real-world LPs?
7 comments
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 . Speedups are relative to Gurobi's cold start.
Table 1. Runtime on four LP-relaxation benchmarks [1].
| Instances | Gurobi cold (ms) ↓ | PDHG-Net E2E (ms) ↓ | AHEAD E2E (ms) ↓ | AHEAD speedup ↑ |
|---|---|---|---|---|
| Small set cover | 28.56 | 31.95 | 6.47 | 4.41× |
| Large set cover | 44.03 | 44.59 | 13.95 | 3.16× |
| Small independent set | 10.22 | 10.44 | 2.53 | 4.04× |
| Large independent set | 10.73 | 11.02 | 2.85 | 3.76× |
| Small facility location | 35.47 | 70.89 | 5.96 | 5.95× |
| Large facility location | 54.09 | TL | 11.60 | 4.66× |
| Small combinatorial auction | 24.92 | 26.01 | 4.66 | 5.35× |
| Large combinatorial auction | 22.96 | 23.35 | 5.14 | 4.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:
- Can AHEAD accelerate practical TE LPs across topologies and sizes?
- 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.
| Network | Nodes | Links | Variables | Constraints | Test instances |
|---|---|---|---|---|---|
| B4 | 12 | 38 | 528 | 170 | 36 |
| ASN98 | 98 | 1,024 | 38.0K | 10.5K | 200 |
| UsCarrier | 158 | 378 | 99.2K | 25.2K | 200 |
| Kdl | 754 | 1,790 | 2.27M | 570K | 50 |
AHEAD and PDHG-Net train only on ASN98 maximum-throughput LPs. All methods use Gurobi GPU-PDHG at accuracy . 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 – zero-shot E2E speedups versus at most for PDHG-Net.
Table 2. Cross-topology generalization on maximum throughput.
| Method | ASN98 | B4 | UsCarrier | Kdl |
|---|---|---|---|---|
| Cold start | 199.1 / 7,854 | 18.67 / 632 | 308.1 / 2,575 | 31,610 / 14,313 |
| PDHG-Net | 215.0 / 8,338 | 20.61 / 538 | 297.8 / 2,493 | 29,990 / 12,953 |
| AHEAD () | 169.2 / 6,602 | 20.68 / 552 | 263.3 / 2,558 | 17,080 / 6,971 |
| AHEAD | 61.0 / 685 | 2.99 / 54 | 125.0 / 85 | 15,540 / 4,381 |
| AHEAD speedup | 3.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.
| Method | Opt. gap (%) ↓ | E2E time (ms) ↓ | Solver iterations ↓ |
|---|---|---|---|
| Cold start | — | 27.62 | 1,121 |
| PDHG-Net | 40.2 | 35.58 | 1,209 |
| AHEAD () | 0.95 | 27.29 | 1,039 |
| AHEAD | <0.001 | 7.44 | 47 |
Opt. gap is the mean relative objective error before solver. AHEAD achieves a 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.
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× 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× speedups. It also transfers to a different LP formulation with a 3.71× speedup.
These results verify the claimed speedups beyond synthetic LPs. Please see our answer to
Q2below 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⊤), q⊤=(h⊤,b⊤), and y=(yG,yA) with yG≥0. The PDHG projections maintain x∈[ℓ,u] and yG≥0. Thus, bound violations do not appear separately in rp. The reduced cost is λ=projΛ(c−K⊤y), where Λ=Λ1×⋯×Λn and Λi is 0, R+, R−, or R when xi has no finite bound, only a finite lower bound, only a finite upper bound, or both. With λ+=maxλ,0 and λ−=max−λ,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.