Abstract:
This talk presents PDLP, a practical first-order method for large-scale linear programming (LP) problems. Built upon the primal-dual hybrid gradient (PDHG) method applied to the minimax formulation of LP, PDLP incorporates several advanced features, including diagonal preconditioning, presolving, adaptive step sizes, adaptive restarting, and feasibility polishing. 

To evaluate PDLP, we introduce a suite of eleven large-scale LP problems, ranging from 0.14 to 6.3 billion nonzeros. Our implementation solves eight of these instances to an optimality gap of 1% within six days on a single machine. We compare PDLP against Gurobi’s barrier method, primal simplex, and dual simplex implementations. Gurobi barrier solves only three instances and exceeds a 1TB RAM limit on the others. While primal and dual simplex methods are more memory efficient, they are much slower, solving only three instances within six days. These results demonstrate the significant advantages of PDLP in solving large-scale LPs efficiently.

Bio:
Oliver is an Assistant Professor in the Industrial Engineering Department at the University of Pittsburgh. Before joining the University of Pittsburgh he was a visiting postdoctoral scholar at Google Research.  He earned his PhD in 2019 under the supervision of Yinyu Ye. His research develops optimization algorithms for solving large-scale machine learning and operations research problems.

Oliver’s work has led to important advances in optimization theory. For instance, his work with Yair Carmon establishing lower bounds on the cost of uncertainty in problem parameters in machine learning received the 2024 Best Paper Award at the Conference on Learning Theory.  

Oliver’s innovations have also driven real-world impact. At Google, he developed the PDLP solver, a cutting-edge first-order method for solving large-scale linear programs. This work earned him and his collaborators the 2024 Beale-Orchard-Hays Prize for computational excellence. PDLP has been widely adopted in industry including at NVIDIA, COPT, and Gurobi.