pith. sign in

arxiv: 2312.14832 · v2 · pith:LUDAYEVYnew · submitted 2023-12-22 · 🧮 math.OC

cuPDLP-C: A Strengthened Implementation of cuPDLP for Linear Programming by C language

Haihao Lu , Jinwen Yang , Haodong Hu , Qi Huangfu , Jinsong Liu , Tianhao Liu , Yinyu Ye , Chuwen Zhang
show 1 more author
Dongdong Ge
This is my paper
classification 🧮 math.OC
keywords cupdlpprogrammingcommercialcomputationallanguagelinearadvantagesalgorithm
0
0 comments X
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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 6 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Accessible Complexity Bounds for Restarted PDHG on Linear Programs with a Unique Optimizer

    math.OC 2024-10 unverdicted novelty 7.0

    Derives accessible O(κΦ ln(κΦ ||w*||/ε)) iteration bound for rPDHG on unique-optima LPs, with computable Φ, two-stage performance, and equivalence to stability and sharpness.

  2. From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal $k$-Sparse GLMs

    cs.LG 2026-05 unverdicted novelty 6.0

    A modular CPU-GPU batching framework for branch-and-bound delivers 10-100x speedups with zero optimality gap when certifying optimal cardinality-constrained GLMs.

  3. A New Crossover Algorithm for LP Inspired by the Spiral Dynamic of PDHG

    math.OC 2024-09 unverdicted novelty 6.0

    A geometric analysis shows PDHG on LP produces a spiral dynamic with orthogonal rotation and forward components, which is used to design a new non-simplex crossover algorithm for vertex solutions.

  4. SDSL-Solver: Scalable Distributed Sparse Linear Solvers for Large-Scale Interior Point Methods

    cs.DC 2026-04 unverdicted novelty 5.0

    SDSL-Solver delivers 6.23x and 7.77x average speedups over PETSc on four nodes for Block Jacobi and BBD modes on sparse systems up to 5 million dimensions in IPMs.

  5. Presolving for GPU-Accelerated First-Order LP Solvers

    math.OC 2026-04 unverdicted novelty 5.0

    A set of simple low-cost presolve rules captures most of Gurobi's reduction and yields end-to-end speedups for GPU first-order LP solvers.

  6. On the power of linear programming for K-means clustering

    math.OC 2024-02 conditional novelty 5.0

    An LP relaxation for K-means is shown to be tight under sufficient conditions for two clusters with recovery guarantees under a stochastic model, plus a scalable cutting-plane algorithm for n up to 4000.