On the Relationships among GPU-Accelerated First-Order Methods for Solving Linear Programming

Source abstract

This paper aims to understand the relationships among recently developed GPU accelerated first-order methods (FOMs) for linear programming (LP), with particular em phasis on HPR-LP—a Halpern Peaceman–Rachford (HPR) method for LP. Our findings can be summarized as follows: (i) the base algorithm of cuPDLPx, a recently released GPU solver, is a special case of the base algorithm of HPR-LP, thereby showing that cuPDLPx is another concrete implementation instance of HPR-LP; (ii) once the active sets have been identified, HPR-LP and EPR-LP—an ergodic PR method for LP—become equiva lent under the same initialization; and (iii) extensive numerical experiments on benchmark datasets demonstrate that HPR-LP achieves the best overall performance among current GPU-accelerated LP solvers. These findings provide a strong motivation for using the HPR method as a baseline to further develop GPU-accelerated LP solvers and beyond.