Timezone: »

 
Poster
Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient
David Applegate · Mateo Diaz · Oliver Hinder · Haihao Lu · Miles Lubin · Brendan O'Donoghue · Warren Schudy

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @
in Poster Session 6 »
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.
Keywords: Optimization

Author Information

David Applegate (Google Research)

David Applegate is a Research Scientist at Google NYC, in the Large Scale Optimization group within the Algorithms and Optimization team. He came to Google in 2016, after 16 years as a Lead Member of Technical Staff in the AT&T Shannon Research Laboratory. Prior to that he spent 4 years as an Associate Professor at Rice University and 4 years as a Member of Technical Staff in AT&T Bell Labs. He has a Ph.D. in Computer Science from Carnegie Mellon (1991) and a B.S. in Computer Science and Math from the University of Dayton (1984).

Mateo Diaz (Cornell University)
Oliver Hinder (University of Pittsburgh)
Haihao Lu (University of Chicago)
Miles Lubin (Google)
Brendan O'Donoghue (DeepMind)
Warren Schudy (Google)

More from the Same Authors