full
search.png

Search

close.png

Cancel

arrow
Volume 43, Issue 5
A DRS-Based Path-Following Algorithm for Linear Programming

Yiyang Liu, Haoyang Liu, Hantao Nie & Zaiwen Wen

DOI: 10.4208/jcm.2508-m2023-0134

J. Comp. Math., 43 (2025), pp. 1141-1168.

Published online: 2025-09

Preview Purchase PDF 12 138

Cited by

google scholar semantic scholar
Export citation
  • Abstract

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.

  • Keywords

Linear programming, Douglas-Rachford splitting, Second-order method, Pathfollowing.

  • AMS Subject Headings

65K05, 90C05, 90C25

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@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 = {

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.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.2508-m2023-0134}, url = {http://global-sci.org/intro/article_detail/jcm/24475.html} }
TY - JOUR T1 - A DRS-Based Path-Following Algorithm for Linear Programming AU - Liu , Yiyang AU - Liu , Haoyang AU - Nie , Hantao AU - Wen , Zaiwen JO - Journal of Computational Mathematics VL - 5 SP - 1141 EP - 1168 PY - 2025 DA - 2025/09 SN - 43 DO - http://doi.org/10.4208/jcm.2508-m2023-0134 UR - https://global-sci.org/intro/article_detail/jcm/24475.html KW - Linear programming, Douglas-Rachford splitting, Second-order method, Pathfollowing. AB -

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.

Liu , YiyangLiu , HaoyangNie , Hantao and Wen , Zaiwen. (2025). A DRS-Based Path-Following Algorithm for Linear Programming. Journal of Computational Mathematics. 43 (5). 1141-1168. doi:10.4208/jcm.2508-m2023-0134
Copy to clipboard
BibteX RIS TXT
The citation has been copied to your clipboard