REVIEW 9 cited by
cuPDLP-C: A Strengthened Implementation of cuPDLP for Linear Programming by C language
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
A recent GPU implementation of the Restarted Primal-Dual Hybrid Gradient Method for Linear Programming was proposed in Lu and Yang (2023). Its computational results demonstrate the significant computational advantages of the GPU-based first-order algorithm on certain large-scale problems. The average performance also achieves a level close to commercial solvers for the first time in history. However, due to limitations in experimental hardware and the disadvantage of implementing the algorithm in Julia compared to C language, neither the commercial solver nor cuPDLP reached their maximum efficiency. Therefore, in this report, we have re-implemented and optimized cuPDLP in C language. Utilizing state-of-the-art CPU and GPU hardware, we extensively compare cuPDLP with the best commercial solvers. The experiments further highlight its substantial computational advantages and potential for solving large-scale linear programming problems. We also discuss the profound impact this breakthrough may have on mathematical programming research and the entire operations research community.
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.
-
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.
-
Scalable First-order Method for Certifying Optimal k-Sparse GLMs
A FISTA-based method with a custom PAVA computes perspective-relaxation dual bounds for k-sparse GLMs in O(p log p) per prox evaluation, enabling larger optimality certificates.
-
A scalable linear programming-based framework for data clustering
LP cutting-plane methods for K-means extend to fair and spectral clustering, certifying 1% optimality on most n≤3000 instances and often beating popular heuristics.
-
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). Sign in to comment.