A DRS-Based Path-Following Algorithm for Linear Programming (Journal of Computational Mathematics, 2025)
In this paper, we present a novel Douglas-Rachford-splitting-based path following(DRS-PF) method that rapidly obtains the solution of linear programming (LP) withhigh accuracy. It originates from the fixed-point mapping associated with DRS on thelog-barrier penalized LP. A path-following scheme is then proposed to simultaneously update the iterates and the penalty parameter for accelerating the overall procedure. Itsglobal convergence towards an optimal solution to the original problem is established under mild assumptions. Numerical experiments show that DRS-PF outperforms the simplexand interior point methods implemented in the academic software (CLP, HiGHS, etc.) interms of the geometric mean of the running time on a few typical benchmark data sets. Insome cases, it is even reasonably competitive to the interior point method implemented inGurobi, one of the most powerful software for LP.
Keywords: Linear programming; Douglas-Rachford splitting; Second-order method; Pathfollowing.