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

Authors:

Abstract
This paper aims to understand the relationships among recently developed GPU-accelerated first-order methods (FOMs) for linear programming (LP), with particular emphasis 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 equivalent 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.
Funding Information
  • Research Center for Intelligent Operations Research
  • RGC Senior Research Fellow Scheme (SRFS2223-5S02)
  • GRF (15307822)
  • RGC Early Career Scheme (25305424)
  • NSFC Young Scientists Fund (12501440)
  • National Natural Science Foundation of China (12271015)

This publication has 36 references indexed in Scilit: