Metraipolis › archive › dc_53a97ee2d0c7
GPU-Accelerated Presolving for Linear Programming — arXiv:2609.16182
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.16182
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T20:43:19.852Z
- SHA-256 of the archived text
f2f40d4d07bccff13e0020ac9f44e1d96ce37d13715cc897241d3d140d05b1d7- Stable URL of this page
https://metraipolis.com/documento/dc_53a97ee2d0c7
How to cite
GPU-Accelerated Presolving for Linear Programming — arXiv:2609.16182 — arXiv (en), https://arxiv.org/abs/2609.16182 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_53a97ee2d0c7 (Metraipolis archive dc_53a97ee2d0c7, sha256 f2f40d4d07bccff13e0020ac9f44e1d96ce37d13715cc897241d3d140d05b1d7)
BibTeX
@misc{dc53a97ee2d0c7,
title = {GPU-Accelerated Presolving for Linear Programming — arXiv:2609.16182},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.16182},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_53a97ee2d0c7; sha256 f2f40d4d07bccff13e0020ac9f44e1d96ce37d13715cc897241d3d140d05b1d7},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.16182. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-16 in math.OC). Categorie arXiv: Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2609.16182 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-15T19:36:35.838Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).