@Article{JCM-43-1141,
author = {Liu , YiyangLiu , HaoyangNie , Hantao and Wen , Zaiwen},
title = {A DRS-Based Path-Following Algorithm for Linear Programming},
journal = {Journal of Computational Mathematics},
year = {2025},
volume = {43},
number = {5},
pages = {1141--1168},
abstract = {<p style="text-align: justify;">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.</p>},
issn = {1991-7139},
doi = {https://doi.org/10.4208/jcm.2508-m2023-0134},
url = {http://global-sci.org/intro/article_detail/jcm/24475.html}
}