Solving Linear Programs with Fast Online Learning Algorithms

Wenzhi Gao, Dongdong Ge, Chunlin Sun, Yinyu Ye
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:10649-10675, 2023.

Abstract

This paper presents fast first-order methods for solving linear programs (LPs) approximately. We adapt online linear programming algorithms to offline LPs and obtain algorithms that avoid any matrix multiplication. We also introduce a variable-duplication technique that copies each variable $K$ times and reduces the optimality gap and constraint violation by a factor of $\sqrt{K}$. Furthermore, we show how online algorithms can be effectively integrated into sifting, a column generation scheme for large-scale LPs. Numerical experiments demonstrate that our methods can serve as either an approximate direct solver, or an initialization subroutine for exact LP solving.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-gao23a, title = {Solving Linear Programs with Fast Online Learning Algorithms}, author = {Gao, Wenzhi and Ge, Dongdong and Sun, Chunlin and Ye, Yinyu}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {10649--10675}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/gao23a/gao23a.pdf}, url = {https://proceedings.mlr.press/v202/gao23a.html}, abstract = {This paper presents fast first-order methods for solving linear programs (LPs) approximately. We adapt online linear programming algorithms to offline LPs and obtain algorithms that avoid any matrix multiplication. We also introduce a variable-duplication technique that copies each variable $K$ times and reduces the optimality gap and constraint violation by a factor of $\sqrt{K}$. Furthermore, we show how online algorithms can be effectively integrated into sifting, a column generation scheme for large-scale LPs. Numerical experiments demonstrate that our methods can serve as either an approximate direct solver, or an initialization subroutine for exact LP solving.} }
Endnote
%0 Conference Paper %T Solving Linear Programs with Fast Online Learning Algorithms %A Wenzhi Gao %A Dongdong Ge %A Chunlin Sun %A Yinyu Ye %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-gao23a %I PMLR %P 10649--10675 %U https://proceedings.mlr.press/v202/gao23a.html %V 202 %X This paper presents fast first-order methods for solving linear programs (LPs) approximately. We adapt online linear programming algorithms to offline LPs and obtain algorithms that avoid any matrix multiplication. We also introduce a variable-duplication technique that copies each variable $K$ times and reduces the optimality gap and constraint violation by a factor of $\sqrt{K}$. Furthermore, we show how online algorithms can be effectively integrated into sifting, a column generation scheme for large-scale LPs. Numerical experiments demonstrate that our methods can serve as either an approximate direct solver, or an initialization subroutine for exact LP solving.
APA
Gao, W., Ge, D., Sun, C. & Ye, Y.. (2023). Solving Linear Programs with Fast Online Learning Algorithms. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:10649-10675 Available from https://proceedings.mlr.press/v202/gao23a.html.

Related Material