Research map / Learning theory and algorithms / Combinatorial and search optimization
PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PDHG-Net, a PDHG-unrolled GNN-like network with channel expansion, and a two-stage inference that warm-starts PDLP from its predictions, reporting up to 3x speedup over PDLP on large LPs.
Problem
Solving large-scale linear programs quickly; first-order methods like PDHG/PDLP are scalable but can be slow, and existing L2O for LP mostly emulates interior-point or simplex methods.
Approach
Unroll the PDHG iterations into a period-2 neural network (primal and dual blocks) with ReLU replacing projections and channel expansion (borrowed from GNNs) for generalization across LP sizes; prove it can exactly reproduce PDHG and approximate LP solutions with O(1/epsilon) neurons, then warm-start PDLP with its output.
Key results
- On PageRank with 1e5 nodes, the framework solves in 22.4s versus 71.3s for PDLP (about 68.6% faster, up to 3x speedup).
- On IP-L, solve time improves 21.7% (7,866.3s vs 10,045.6s) and iterations improve 27.8% over PDLP.
- On larger-than-training instances, average acceleration is about 31.1% in time and 31.8% in iterations over PDLP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Warm-start PDLP with PDHG-Net predictions instead of default initialization | PDLP · PageRank | solve time: 64.3% faster on average | Helped |
| Warm-start PDLP with PDHG-Net predictions instead of default initialization | PDLP · IP-S | solve time: 11.4 -> 9.2; ↑ 19.5% | Helped |
| Warm-start PDLP with PDHG-Net predictions instead of default initialization | PDLP · IP-L | solve time: 10,045.6 -> 7,866.3; ↑ 21.7% | Helped |
| Warm-start PDLP with PDHG-Net predictions instead of default initialization | PDLP · WA-S | solve time: 137.8 -> 114.7; ↑ 16.7% | Helped |
| Warm-start PDLP with PDHG-Net predictions instead of default initialization | PDLP · WA-L | solve time: 6426.2 -> 4817.6; ↑ 25.0% | Helped |
| Use PDHG-Net rather than GNN to generate warm-start predictions | PDLP warm-start · PageRank, 10^5 nodes | solve time improvement over PDLP: ↑71.3% vs ↓ 4.0% | Mixed |
Surprising findings
- The GNN variant reduces PDLP's time improvement to negative (-4.0%) at 1e5 nodes, while PDHG-Net gives 71.3%.
- Gurobi exceeded 15,000s on PageRank instances of 1e5 nodes and above, and ABIP failed at 1e6 nodes.
Limitations
- Gains depend on having enough historical LP instances for training; the paper notes benefits when enough historical data exists.
- Gains on the WA-large generalization test are small (4.4% time).
- Only PageRank, IP and WA datasets are evaluated; the approach is not tested on MIP.
Experimental setup
Datasets: PageRank Item Placement (IP) Workload Appropriation (WA)
Benchmarks: PageRank LP instances IP-S IP-L WA-S WA-L
Metrics: solve time (sec) number of iterations improvement ratio l2 distance to optimal solution number of restarts
Baselines: PDLP Gurobi ABIP GNN
Builds on: PDHG (Chambolle-Pock) PDLP deep unrolling (ISTA/LISTA) GNN-based L2O for LP
Closest papers by meaning
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.88)
- Learning Initial Basis Selection for Linear Programming via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision (ICML 2025 · similarity 0.86)
- Learning Generalized Linear Programming Value Functions (NeurIPS 2024 · similarity 0.86)
- Learning to Generate Projections for Reducing Dimensionality of Heterogeneous Linear Programming Problems (ICML 2025 · similarity 0.85)
- Principled Data Augmentation for Learning to Solve Quadratic Programming Problems (NeurIPS 2025 · similarity 0.84)
- Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.