H-PDLP: GPU-Accelerated Linear Programming via Generalized PDHG and Homogeneous Self-Dual Embedding
Abstract
GPU-based first-order methods are emerging as an approach for solving large-scale linear programming (LP) problems. We present H-PDLP, a GPU first-order LP solver based on a generalized primal-dual hybrid gradient (PDHG) method for a homogeneous self-dual embedding of the LP, and study its numerical performance. The solver applies the restarted reflected Halpern iteration to the generalized PDHG operator, with the embedding encoding both primal-dual optimal solutions and certificates of primal or dual infeasibility. We derive a compact embedding for LPs with two-sided constraint and variable bounds in which the bounds enter through box cones, and we show that the resulting box-cone projections reduce to one-dimensional root-finding problems, so that each iteration remains matrix-free and well suited to GPUs. On the theoretical side, we establish conditions under which the iterates remain uniformly bounded away from the trivial zero solution of the embedding and derive complexity guarantees for the method. We also introduce MIPLIBInfeas, a reproducible benchmark of 229 infeasible and 105 unbounded LPs derived from MIPLIB 2017. Numerical experiments demonstrate the effectiveness of the proposed approach on both feasible LPs and infeasible or unbounded LPs. The source code for H-PDLP is publicly available at https://github.com/MIT-Lu-Lab/H-PDLP.
Related
- A One-Factorization Predictor-Corrector Long-Step Arc-Search Method and a Curvature-Amplified Variant for Semidefinite Programming with a Homogeneous Self-Dual Embedding
- GPU-Accelerated Presolving for Linear Programming
- 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
BibTeX
@misc{lu2026hpdlp,
title = {{H-PDLP: GPU-Accelerated Linear Programming via Generalized PDHG and Homogeneous Self-Dual Embedding}},
author = {Haihao Lu and Bo Tang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17695},
eprint = {2610.17695},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17695},
}
RIS
TY - UNPB
TI - H-PDLP: GPU-Accelerated Linear Programming via Generalized PDHG and Homogeneous Self-Dual Embedding
AU - Haihao Lu
AU - Bo Tang
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.17695
UR - https://arxiv.org/abs/2610.17695
AB - GPU-based first-order methods are emerging as an approach for solving large-scale linear programming (LP) problems. We present H-PDLP, a GPU first-order LP solver based on a generalized primal-dual hybrid gradient (PDHG) method for a homogeneous self-dual embedding of the LP, and study its numerical performance. The solver applies the restarted reflected Halpern iteration to the generalized PDHG operator, with the embedding encoding both primal-dual optimal solutions and certificates of primal or dual infeasibility. We derive a compact embedding for LPs with two-sided constraint and variable bounds in which the bounds enter through box cones, and we show that the resulting box-cone projections reduce to one-dimensional root-finding problems, so that each iteration remains matrix-free and well suited to GPUs. On the theoretical side, we establish conditions under which the iterates remain uniformly bounded away from the trivial zero solution of the embedding and derive complexity guarantees for the method. We also introduce MIPLIBInfeas, a reproducible benchmark of 229 infeasible and 105 unbounded LPs derived from MIPLIB 2017. Numerical experiments demonstrate the effectiveness of the proposed approach on both feasible LPs and infeasible or unbounded LPs. The source code for H-PDLP is publicly available at https://github.com/MIT-Lu-Lab/H-PDLP.
ER -