(untitled) (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) with high accuracy. It originates from the fixed-point mapping associated with DRS on the log-barrier penalized LP. A path-following scheme is then proposed to simultaneously update the iterates and the penalty parameter for accelerating the overall procedure. Its global convergence towards an optimal solution to the original problem is established under mild assumptions. Numerical experiments show that DRS-PF outperforms the simplex and interior point methods implemented in the academic software (CLP, HiGHS, etc.) in terms of the geometric mean of the running time on a few typical benchmark data sets. In some cases, it is even reasonably competitive to the interior point method implemented in Gurobi, one of the most powerful software for LP.