Metraipolis › archive › dc_e2f7bd49578e
GPU-Accelerated Preprocessing for Large-Scale Linear Programming — arXiv:2610.19840
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.19840
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T14:25:35.605Z
- SHA-256 of the archived text
2ba1f683de48e0955d7d61311427c42a8f32fd2581535c1e56247d46d0bdeadb- Stable URL of this page
https://metraipolis.com/documento/dc_e2f7bd49578e
How to cite
GPU-Accelerated Preprocessing for Large-Scale Linear Programming — arXiv:2610.19840 — arXiv (en), https://arxiv.org/abs/2610.19840 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e2f7bd49578e (Metraipolis archive dc_e2f7bd49578e, sha256 2ba1f683de48e0955d7d61311427c42a8f32fd2581535c1e56247d46d0bdeadb)
BibTeX
@misc{dce2f7bd49578e,
title = {GPU-Accelerated Preprocessing for Large-Scale Linear Programming — arXiv:2610.19840},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.19840},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e2f7bd49578e; sha256 2ba1f683de48e0955d7d61311427c42a8f32fd2581535c1e56247d46d0bdeadb},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.19840. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
GPU-accelerated first-order methods are increasingly effective for solving large-scale linear programs (LPs), yet LP preprocessing remains predominantly CPU-based and can become costly. A key challenge is that dependencies among presolve reductions and frequent modifications to sparse LP data make efficient GPU parallelization difficult. To address this challenge, we develop GPU-Preprocessor, a GPU-native LP preprocessing framework that integrates folding and presolve. To efficiently implement folding on GPUs, we adapt a randomized partition refinement algorithm to LP folding, using sparse matrix-vector products and parallel sorting to construct stable row and column partitions. For presolve, we introduce a new piecewise-linear reformulation rule that exploits underlying convex piecewise-linear structure to obtain sparser LP representations. We also develop a framework that combines phase scheduling with a Scan-Plan-Apply design to coordinate presolve rules and reduce sparse-matrix reconstruction overhead through batched updates. Numerical experiments on three LP benchmark sets show that GPU-Preprocessor achieves greater average problem-size reductions than PSLP and Gurobi Presolve, with SGM10 preprocessing-time speedups of up to $43.9\times$ and $677.7\times$, respectively. Here, SGM10 denotes the shifted geometric mean with a 10-second shift. On the largest tested quadratic assignment problem LP relaxation, these speedups reach $126.3\times$ and $2{,}207.9\times$. When integrated with the GPU-accelerated LP solver HPR-LP, GPU-Preprocessor achieves SGM10 speedups of $2.5\times$ to $5.0\times$ in combined preprocessing and solving time over HPR-LP without preprocessing. The code is available at this https URL .
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2610.19840 — 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-15T13:55:20.327Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).