Collaborative Research: Scaling up Linear Programming with First-Order Methods and MPI-White Paper Tracking Number: 23-000004742
Abstract
(Approved for public release)This project aims to devise distributed-memory parallel algorithms and software for solving linear programming (LP) problems much larger than current commercial and open-source solvers currently handle. Such technology should enable the solution of a wide variety of currently intractable problems throughout industry, the military, and the public sector. Our basic approach will be to build on recent advances in first-order optimization methods, in combination with new implementation techniques.An initial task of the project will be to produce a truly scalable implementation of PDLP, a recently developed LP specialization of the primal-dual hybrid gradient (PDHG) first-order method. The implementation will employ a new MPI-based software framework that we plan to develop, using new distributed sparse matrix multiplication techniques and vector representations. In parallel with the project s software and experimental work, we will enhance the current theoretical understanding of PDLP/PDHG, and use this knowledge to improve the algorithms we implement. The new software framework will provide an ideal substrate for experimental work on a wide variety of first-order optimization methods beside PDHG/PDLP, including (but not limited to) various forward-backward methods, projective splitting algorithms, and approximate ADMM algorithms. We will study such methods application to LP both theoretically and empirically, as they may benefit from the same kind of careful theoretical study and empirical tuning already applied to PDLP. Finally,by exploiting the basis structure of optimal LP solutions, we will investigate techniques for truncating the slow tail convergence that often afflicts first-order methods, prospectively attempting to "jump" to optimal solutions near the current algorithm iterate.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Nov 09, 2024
- Source ID
- N000142412735
Entities
People
- Haihao Lu
Organizations
- Massachusetts Institute of Technology
- Office of Naval Research
- United States Navy