REVIEW 9 cited by
cuPDLP.jl: A GPU Implementation of Restarted Primal-Dual Hybrid Gradient for Linear Programming in Julia
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original 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 (PDHG) 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.
Forward citations
Cited by 9 Pith papers
-
Gradient Methods with Online Scaling Part I. Theoretical Foundations
Online scaled gradient methods adapt matrix step sizes via online learning, match the best fixed step size asymptotically, and achieve non-asymptotic superlinear convergence on smooth strongly convex problems.
-
New Understandings and Computation on Augmented Lagrangian Methods for Low-Rank Semidefinite Programming
Augmented Lagrangian subproblems inherit low-rankness, strict complementarity, and quadratic growth from a primal simple SDP, making Burer-Monteiro gradient descent converge linearly.
-
Large-Scale Network Utility Maximization via GPU-Accelerated Proximal Message Passing
A GPU-accelerated ADMM variant, proximal message passing, is shown to solve large network utility maximization problems with log and linear utilities faster and at larger scale than existing solvers.
-
HPR-QP: A dual Halpern Peaceman-Rachford method for solving large-scale convex composite quadratic programming
HPR-QP solves large-scale convex composite quadratic programs with a dual Halpern Peaceman-Rachford iteration on the restricted Wolfe dual, obtaining O(1/k) KKT residual and strong GPU benchmark results.
-
Enhanced PDHG for Linear Programming with Online Preconditioning
Online preconditioning for a GPU LP solver cuts iteration counts by roughly 10-30% on Netlib and MIPLIB benchmarks, with the learning rate tuned per instance.
-
PDHCG: A Scalable First-Order Method for Large-Scale Competitive Market Equilibrium Computation
A restarted primal-dual method with a per-buyer bisection inner solve, run on GPUs, computes Fisher equilibria at ten-million-buyer scale and extends to Arrow-Debreu markets via fixed-point iteration.
-
TSENOR: Highly-Efficient Algorithm for Finding Transposable N:M Sparse Masks
TSENOR computes transposable N:M masks up to hundreds of times faster than prior solvers by combining entropy-regularized optimal transport with a greedy plus local search rounding.
-
Accelerating a Linear Programming Algorithm on AMD GPUs
A PyTorch/ROCm implementation of PDHG, torchPDLP, achieves up to 36x speedup over its own CPU version on large linear programs, with a novel but inconsistent multi-start heuristic called fishnet casting.
-
An Overview of GPU-based First-Order Methods for Linear Programming and Extensions
A survey of GPU-based first-order LP solvers focusing on cuPDLP, its PDHG core, theory, benchmarks, and extensions to QP, SDP, and conic programming.
Discussion (0). Continue with ORCID to comment.