HPR-LP: An implementation of an HPR method for solving linear programming
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915199128174592 |
|---|---|
| author | Chen, Kaihuang Sun, Defeng Yuan, Yancheng Zhang, Guojun Zhao, Xinyuan |
| author_facet | Chen, Kaihuang Sun, Defeng Yuan, Yancheng Zhang, Guojun Zhao, Xinyuan |
| contents | In this paper, we introduce an HPR-LP solver, an implementation of a Halpern Peaceman-Rachford (HPR) method with semi-proximal terms for solving linear programming (LP). The HPR method enjoys the iteration complexity of $O(1/k)$ in terms of the Karush-Kuhn-Tucker residual and the objective error. Based on the complexity results, we design an adaptive strategy of restart and penalty parameter update to improve the efficiency and robustness of the HPR method. We conduct extensive numerical experiments on different LP benchmark datasets using NVIDIA A100-SXM4-80GB GPU in different stopping tolerances. Our solver's Julia version achieves a $\textbf{2.39x}$ to $\textbf{5.70x}$ speedup measured by SGM10 on benchmark datasets with presolve ($\textbf{2.03x}$ to $\textbf{4.06x}$ without presolve) over the award-winning solver PDLP with the tolerance of $10^{-8}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_12179 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | HPR-LP: An implementation of an HPR method for solving linear programming Chen, Kaihuang Sun, Defeng Yuan, Yancheng Zhang, Guojun Zhao, Xinyuan Optimization and Control 90C05, 90C06, 90C25, 65Y20 In this paper, we introduce an HPR-LP solver, an implementation of a Halpern Peaceman-Rachford (HPR) method with semi-proximal terms for solving linear programming (LP). The HPR method enjoys the iteration complexity of $O(1/k)$ in terms of the Karush-Kuhn-Tucker residual and the objective error. Based on the complexity results, we design an adaptive strategy of restart and penalty parameter update to improve the efficiency and robustness of the HPR method. We conduct extensive numerical experiments on different LP benchmark datasets using NVIDIA A100-SXM4-80GB GPU in different stopping tolerances. Our solver's Julia version achieves a $\textbf{2.39x}$ to $\textbf{5.70x}$ speedup measured by SGM10 on benchmark datasets with presolve ($\textbf{2.03x}$ to $\textbf{4.06x}$ without presolve) over the award-winning solver PDLP with the tolerance of $10^{-8}$. |
| title | HPR-LP: An implementation of an HPR method for solving linear programming |
| topic | Optimization and Control 90C05, 90C06, 90C25, 65Y20 |
| url | https://arxiv.org/abs/2408.12179 |