# PDLP: A Practical First-Order Method for Large-Scale Linear Programming

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jan 2025.

## Built on by (most cited first, 4 of 4)

- [Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verification](https://mlsanity.com/paper/2512.11087/) (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)
- [Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming](https://mlsanity.com/paper/2610.01546/) (2026)

## Abstract (arXiv)

We present PDLP, a practical first-order method for linear programming (LP) designed to solve large-scale LP problems. PDLP is based on the primal-dual hybrid gradient (PDHG) method applied to the minimax formulation of LP. PDLP incorporates several enhancements to PDHG, including diagonal preconditioning, presolving, adaptive step sizes, adaptive restarting, and feasibility polishing. Our algorithm is implemented in C++, available in Google's open-source OR-Tools library, and supports multithreading. To evaluate our method, we introduce a new collection of eleven large-scale LP problems with sizes ranging from 125 million to 6.3 billion nonzeros. PDLP solves eight of these instances to optimality gaps of 1% (with primal and dual feasibility errors of less than 10-8) within six days on a single machine. We also compare PDLP with Gurobi barrier, primal simplex, and dual simplex implementations. These traditional methods are designed to solve linear programs to much tighter optimality gaps but struggle to solve these instances. Gurobi barrier solves only three instances, exceeding our 1TB RAM limit on the other eight. While primal and dual simplex are more memory-efficient than the barrier method, they are slower and solve only three instances within six days. Compared with the conference version of this work (in: Advances in Neural Information Processing Systems 34 (NeurIPS 2021)), the key new contributions are: (i) feasibility polishing, a technique that quickly finds solutions that are approximately optimal but almost exactly feasible (without which only two of the eleven problems can be solved); (ii) a multithreaded C++ implementation available in Google OR-Tools; and (iii) a new collection of large-scale LP problems. Note that the conference version should be referred to for comparisons with SCS and ablation studies, which we do not repeat in this paper.