GPU-Accelerated Preprocessing for Large-Scale Linear Programming
Abstract
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× and 677.7×, 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× and 2,207.9×. When integrated with the GPU-accelerated LP solver HPR-LP, GPU-Preprocessor achieves SGM10 speedups of 2.5× to 5.0× in combined preprocessing and solving time over HPR-LP without preprocessing. The code is available at https://github.com/PolyU-IOR/GPU-Preprocessor.
Related
- cuPDQPx: A GPU-Accelerated Restarted Halpern PDHG for Large-Scale Convex Quadratic Programming
- PDLP: a practical first-order method for large-scale linear programming
- Recent Developments in HPR Methods for Large-Scale Linear Programming
- AHEAD: Adaptive Neural Acceleration for Large-Scale Linear Programming
- GPU-Accelerated Presolving for Linear Programming
BibTeX
@misc{chen2026gpuaccelerated,
title = {{GPU-Accelerated Preprocessing for Large-Scale Linear Programming}},
author = {Kaihuang Chen and Jiawei Lu and Defeng Sun and Yancheng Yuan and Guojun Zhang and Xiangyu Zhang and Xinyuan Zhao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19840},
eprint = {2610.19840},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19840},
}
RIS
TY - UNPB
TI - GPU-Accelerated Preprocessing for Large-Scale Linear Programming
AU - Kaihuang Chen
AU - Jiawei Lu
AU - Defeng Sun
AU - Yancheng Yuan
AU - Guojun Zhang
AU - Xiangyu Zhang
AU - Xinyuan Zhao
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.19840
UR - https://arxiv.org/abs/2610.19840
AB - 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× and 677.7×, 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× and 2,207.9×. When integrated with the GPU-accelerated LP solver HPR-LP, GPU-Preprocessor achieves SGM10 speedups of 2.5× to 5.0× in combined preprocessing and solving time over HPR-LP without preprocessing. The code is available at https://github.com/PolyU-IOR/GPU-Preprocessor.
ER -