# Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient

arXiv: https://arxiv.org/abs/2106.04756 · HTML: https://mlsanity.com/paper/2106.04756/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2021.

## Built on by (most cited first, 30 of 32)

- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming](https://mlsanity.com/paper/2406.01908/) (2024)
- [Gradient Methods with Online Scaling](https://mlsanity.com/paper/2411.01803/) (2024)
- [Coordinate Linear Variance Reduction for Generalized Linear Programming](https://mlsanity.com/paper/2111.01842/) (2021)
- [Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming](https://mlsanity.com/paper/2309.00203/) (2023)
- [Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verification](https://mlsanity.com/paper/2512.11087/) (2025)
- [Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learning](https://mlsanity.com/paper/2310.11845/) (2023)
- [Machine Learning Insides OptVerse AI Solver: Design Principles and Applications](https://mlsanity.com/paper/2401.05960/) (2024)
- [MPAX: Mathematical Programming in JAX](https://mlsanity.com/paper/2412.09734/) (2024)
- [Provably data-driven projection method for quadratic programming](https://mlsanity.com/paper/2509.04524/) (2025)
- [Dual Interior Point Optimization Learning](https://mlsanity.com/paper/2402.02596/) (2024)
- [Towards graph neural networks for provably solving convex optimization problems](https://mlsanity.com/paper/2502.02446/) (2025)
- [Gradient Methods with Online Scaling Part I. Theoretical Foundations](https://mlsanity.com/paper/2505.23081/) (2025)
- [Federated ADMM from Bayesian Duality](https://mlsanity.com/paper/2506.13150/) (2025)
- [Enforcing convex constraints in Graph Neural Networks](https://mlsanity.com/paper/2510.11227/) (2025)
- [Relaxation-Informed Training of Neural Network Surrogate Models](https://mlsanity.com/paper/2604.22746/) (2026)
- [Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for Linear Programming](https://mlsanity.com/paper/2111.05530/) (2021)
- [Scalable First-order Method for Certifying Optimal k-Sparse GLMs](https://mlsanity.com/paper/2502.09502/) (2025)
- [Nonlinear Optimization with GPU-Accelerated Neural Network Constraints](https://mlsanity.com/paper/2509.22462/) (2025)
- [Learning to Optimize by Differentiable Programming](https://mlsanity.com/paper/2601.16510/) (2026)
- [Batched First-Order Methods for Parallel LP Solving in MIP](https://mlsanity.com/paper/2601.21990/) (2026)
- [Design and Implementation of an Heuristic-Enhanced Branch-and-Bound Solver for MILP](https://mlsanity.com/paper/2206.01857/) (2022)
- [Neural Optimization with Adaptive Heuristics for Intelligent Marketing System](https://mlsanity.com/paper/2405.10490/) (2024)
- [Perturbing the Derivative: Wild Refitting for Model-Free Evaluation of Machine Learning Models under Bregman Losses](https://mlsanity.com/paper/2509.02476/) (2025)
- [Feature Augmentation of GNNs for ILPs: Local Uniqueness Suffices](https://mlsanity.com/paper/2509.21000/) (2025)
- [Petri Net Relaxation for Infeasibility Explanation and Sequential Task Planning](https://mlsanity.com/paper/2602.22094/) (2026)
- [From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal k-Sparse GLMs](https://mlsanity.com/paper/2605.22188/) (2026)
- [Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programming](https://mlsanity.com/paper/2606.08638/) (2026)
- [GPU-Enabled Large-Scale Optimization Using Randomized Linear Algebra](https://mlsanity.com/paper/2609.08136/) (2026)
- [Dual-guided Hierarchical Edge Localization for Large-scale Optimal Transport Across Dimensions](https://mlsanity.com/paper/2609.13010/) (2026)

## Abstract (arXiv)

We present PDLP, a practical first-order method for linear programming (LP) that can solve to the high levels of accuracy that are expected in traditional LP applications. In addition, it can scale to very large problems because its core operation is matrix-vector multiplications. PDLP is derived by applying the primal-dual hybrid gradient (PDHG) method, popularized by Chambolle and Pock (2011), to a saddle-point formulation of LP. PDLP enhances PDHG for LP by combining several new techniques with older tricks from the literature; the enhancements include diagonal preconditioning, presolving, adaptive step sizes, and adaptive restarting. PDLP improves the state of the art for first-order methods applied to LP. We compare PDLP with SCS, an ADMM-based solver, on a set of 383 LP instances derived from MIPLIB 2017. With a target of 10-8 relative accuracy and 1 hour time limit, PDLP achieves a 6.3x reduction in the geometric mean of solve times and a 4.6x reduction in the number of instances unsolved (from 227 to 49). Furthermore, we highlight standard benchmark instances and a large-scale application (PageRank) where our open-source prototype of PDLP, written in Julia, outperforms a commercial LP solver.