Solving Linear Programs with Fast Online Learning Algorithms
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
Text
Gao et al. "Solving Linear Programs with Fast Online Learning Algorithms." International Conference on Machine Learning, 2023.Markdown
[Gao et al. "Solving Linear Programs with Fast Online Learning Algorithms." International Conference on Machine Learning, 2023.](https://mlanthology.org/icml/2023/gao2023icml-solving/)BibTeX
@inproceedings{gao2023icml-solving,
title = {{Solving Linear Programs with Fast Online Learning Algorithms}},
author = {Gao, Wenzhi and Ge, Dongdong and Sun, Chunlin and Ye, Yinyu},
booktitle = {International Conference on Machine Learning},
year = {2023},
pages = {10649-10675},
volume = {202},
url = {https://mlanthology.org/icml/2023/gao2023icml-solving/}
}