GPU-Accelerated Presolving for Linear Programming
Abstract
Recent research has focused on developing GPU-accelerated algorithms for solving linear programs (LPs), with results that are nothing short of extraordinary. But a complete solver pipeline consists of more than the core algorithm, and the elephant in the room is that stages such as presolve have remained on the CPU, where they have become an increasingly large bottleneck. Presolve has stayed on the CPU because of the longstanding view, held by academic and industrial developers alike, that it is inherently sequential and irregular, and therefore difficult to parallelize efficiently. In this paper we challenge this view and show that presolving can benefit substantially from GPU acceleration. We describe simple design principles that avoid severe load imbalance and expose parallelism in reductions that appear inherently sequential. We implement these principles in cuPSLP, a GPU-accelerated version of PSLP, a CPU-based presolver that is itself several times faster than a state-of-the-art commercial presolver. In our experiments, cuPSLP reduces the shifted geometric mean presolve time of PSLP by a factor of 11 on the Mittelmann LP benchmark set and 42 on the GAMS large-scale LP benchmark set, with similar reduction quality.
Related
- H-PDLP: GPU-Accelerated Linear Programming via Generalized PDHG and Homogeneous Self-Dual Embedding
- GPU-Accelerated Preprocessing for Large-Scale Linear Programming
- Accelerated Benders decomposition for bi-objective mixed integer programming
- cuPDQPx: A GPU-Accelerated Restarted Halpern PDHG for Large-Scale Convex Quadratic Programming
- PDLP: a practical first-order method for large-scale linear programming
BibTeX
@misc{cederberg2026gpuaccelerated,
title = {{GPU-Accelerated Presolving for Linear Programming}},
author = {Daniel Cederberg and Stephen Boyd},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.16182},
eprint = {2609.16182},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.16182},
}
RIS
TY - UNPB
TI - GPU-Accelerated Presolving for Linear Programming
AU - Daniel Cederberg
AU - Stephen Boyd
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.16182
UR - https://arxiv.org/abs/2609.16182
AB - Recent research has focused on developing GPU-accelerated algorithms for solving linear programs (LPs), with results that are nothing short of extraordinary. But a complete solver pipeline consists of more than the core algorithm, and the elephant in the room is that stages such as presolve have remained on the CPU, where they have become an increasingly large bottleneck. Presolve has stayed on the CPU because of the longstanding view, held by academic and industrial developers alike, that it is inherently sequential and irregular, and therefore difficult to parallelize efficiently. In this paper we challenge this view and show that presolving can benefit substantially from GPU acceleration. We describe simple design principles that avoid severe load imbalance and expose parallelism in reductions that appear inherently sequential. We implement these principles in cuPSLP, a GPU-accelerated version of PSLP, a CPU-based presolver that is itself several times faster than a state-of-the-art commercial presolver. In our experiments, cuPSLP reduces the shifted geometric mean presolve time of PSLP by a factor of 11 on the Mittelmann LP benchmark set and 42 on the GAMS large-scale LP benchmark set, with similar reduction quality.
ER -