Research map / Optimization / Optimizers
Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient
David Applegate, Mateo Diaz Diaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O'Donoghue, Warren Schudy
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add restarts, scaling, primal weight, adaptive step size and presolve to baseline PDHG (ablation) | PDHG · MIP Relaxations 1e-8, 100k KKT passes | instances solved: 50 -> 283 | Improved |
| use PDLP instead of SCS ADMM solver | PDLP · MIP Relaxations 1e-8, 1h | unsolved instances: 227 -> 49 | Improved |
| use PDLP instead of SCS | PDLP · MIP Relaxations 1e-8, 1h | SGM solve time: 6.3x reduction | Improved |
| each enhancement added to PDHG (presolve excepted on LP benchmark at 1e-4) (ablation) | PDHG · MIP Relaxations/LP benchmark/Netlib | normalized KKT passes | Improved |
| use PDLP instead of Gurobi on PageRank 10^5 nodes | PDLP · PageRank | solve time: 7.8 hr. -> 35 sec. | Improved |
| use PDLP instead of SCS on largest PageRank (10^7) | PDLP · PageRank | solve time: 3.8 hr. vs 5.4 hr. | Hurt |
| use PDLP instead of Gurobi on typical instances | PDLP · MIP Relaxations/LP benchmark | solve time | Mixed |
Closest papers by meaning
- Faster Randomized Interior Point Methods for Tall/Wide Linear Programs (JMLR 2022 · similarity 0.88)
- PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming (ICML 2024 · similarity 0.86)
- Learning Initial Basis Selection for Linear Programming via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision (ICML 2025 · similarity 0.85)
- B$^3$-PWL: GPU-Batched Branch-and-Bound for Piecewise-Linear Optimization with SOS2 Constraints (NeurIPS 2026 · similarity 0.84)
- Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching (ICML 2024 · similarity 0.84)
- From Inverse Optimization to Feasibility to ERM (ICML 2024 · 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.
