cuPDLP.jl: A GPU Implementation of Restarted Primal-Dual Hybrid Gradient for Linear Programming in Julia
Operations Research · 2025 · Volume 73 · Issue 6
Abstract
In this paper, we provide an affirmative answer to the long-standing question: Are GPUs useful in solving linear programming? We present cuPDLP.jl, a GPU implementation of restarted primal-dual hybrid gradient for solving linear programming (LP). We show that this prototype implementation in Julia has comparable numerical performance on standard LP benchmark sets to Gurobi, a highly optimized implementation of the simplex and interior-point methods. This demonstrates the power of using GPUs in linear programming, which, for the first time, showcases that GPUs and first-order methods can lead to performance comparable to state-of-the-art commercial optimization LP solvers on standard benchmark sets. Funding: This work was partially supported by the Air Force Office of Scientific Research [Grant FA9550-24-1-0051]. Supplemental Review: The empirical results in this paper were replicated. The code, data, and files required to reproduce the results were reviewed and are available at 10.1287/opre.2024.1069.cd . Supplemental Material: This article includes an online appendix, computer code and data supporting the study’s findings, and replication files. All supplemental materials, including the code, data, and files required to reproduce the results, are available at 10.1287/opre.2024.1069.cd .
Keywords
Optimization, linear programming, first-order methods, GPUs
Enable JavaScript for citation tools and additional paper interactions.