HPR-LP: A GPU Solver for Linear Programming

Kaihuang Chen, Defeng Sun, Yancheng Yuan, Guojun Zhang, Xinyuan Zhao

Contact: {kaihuang.chen, guojun.zhang}@connect.polyu.hk, {yancheng.yuan, defeng.sun}@polyu.edu.hk, xyzhao@bjut.edu.cn

Find the open-source solver at https://github.com/PolyU-IOR/HPR-LP

Overview

HPR-LP is a Julia implementation of the Halpern Peaceman-Rachford (HPR) method for solving linear programming (LP) problems on the GPU. It is designed to efficiently handle large-scale LP problems with the following formulation:

\[ \begin{array}{ll} \underset{x \in \mathbb{R}^n}{\min} \quad & \langle c, x \rangle \\ \text{s.t.} \quad & A_1 x = b_1, \\ & A_2 x \geq b_2, \\ & l \leq x \leq u . \end{array} \]

Numerical Performance of HPR-LP Compared to Other Solvers

HPR-LP runs fast on an NVIDIA A100-SXM4-80GB GPU! 😊 It outperforms other solvers like cuPDLP.jl in both computational efficiency and solution accuracy.

Numerical performance of HPR-LP.jl and cuPDLP.jl on 49 instances of Mittelmann's LP benchmark set with Gurobi's presolve
Tolerance	1e-4		1e-6		1e-8
Tolerance	SGM10	Solved	SGM10	Solved	SGM10	Solved
cuPDLP.jl	60.0	46	118.6	45	220.6	43
HPR-LP.jl	17.4	49	31.8	49	59.4	48

SGM10 of HPR-LP.jl and cuPDLP.jl on 20 QAP instances (LP relaxation) with Gurobi's presolve
Tolerance	1e-4	1e-6	1e-8
cuPDLP.jl	12.7	60.0	343.1
HPR-LP.jl	2.9	8.8	60.2

Citation

        @article{chen2024hpr,

        title={HPR-LP: An implementation of an HPR method for solving linear programming},

        author={Chen, Kaihuang and Sun, Defeng and Yuan, Yancheng and Zhang, Guojun and Zhao, Xinyuan},

        journal={arXiv preprint arXiv:2408.12179},

        year={2024}

        }