ECLIPSE: An Extreme-Scale Linear Program Solver for Web-Applications

Kinjal Basu, Amol Ghoting, Rahul Mazumder, Yao Pan
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:704-714, 2020.

Abstract

Key problems arising in web applications (with millions of users and thousands of items) can be formulated as linear programs involving billions to trillions of decision variables and constraints. Despite the appeal of linear program (LP) formulations, solving problems at these scales appear to be well beyond the capabilities of existing LP solvers. Often ad-hoc decomposition rules are used to approximately solve these LPs, which have limited optimality guarantees and may lead to sub-optimal performance in practice. In this work, we propose a distributed solver that solves a perturbation of the LP problems at scale via a gradient-based algorithm on the smooth dual of the perturbed LP. The main workhorses of our algorithm are distributed matrix-vector multiplications (with load balancing) and efficient projection operations on distributed machines. Experiments on real-world data show that our proposed LP solver, ECLIPSE, can solve problems with $10^{12}$ decision variables – well beyond the capabilities of current solvers.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-basu20a, title = {{ECLIPSE}: An Extreme-Scale Linear Program Solver for Web-Applications}, author = {Basu, Kinjal and Ghoting, Amol and Mazumder, Rahul and Pan, Yao}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {704--714}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/basu20a/basu20a.pdf}, url = {https://proceedings.mlr.press/v119/basu20a.html}, abstract = {Key problems arising in web applications (with millions of users and thousands of items) can be formulated as linear programs involving billions to trillions of decision variables and constraints. Despite the appeal of linear program (LP) formulations, solving problems at these scales appear to be well beyond the capabilities of existing LP solvers. Often ad-hoc decomposition rules are used to approximately solve these LPs, which have limited optimality guarantees and may lead to sub-optimal performance in practice. In this work, we propose a distributed solver that solves a perturbation of the LP problems at scale via a gradient-based algorithm on the smooth dual of the perturbed LP. The main workhorses of our algorithm are distributed matrix-vector multiplications (with load balancing) and efficient projection operations on distributed machines. Experiments on real-world data show that our proposed LP solver, ECLIPSE, can solve problems with $10^{12}$ decision variables – well beyond the capabilities of current solvers.} }
Endnote
%0 Conference Paper %T ECLIPSE: An Extreme-Scale Linear Program Solver for Web-Applications %A Kinjal Basu %A Amol Ghoting %A Rahul Mazumder %A Yao Pan %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-basu20a %I PMLR %P 704--714 %U https://proceedings.mlr.press/v119/basu20a.html %V 119 %X Key problems arising in web applications (with millions of users and thousands of items) can be formulated as linear programs involving billions to trillions of decision variables and constraints. Despite the appeal of linear program (LP) formulations, solving problems at these scales appear to be well beyond the capabilities of existing LP solvers. Often ad-hoc decomposition rules are used to approximately solve these LPs, which have limited optimality guarantees and may lead to sub-optimal performance in practice. In this work, we propose a distributed solver that solves a perturbation of the LP problems at scale via a gradient-based algorithm on the smooth dual of the perturbed LP. The main workhorses of our algorithm are distributed matrix-vector multiplications (with load balancing) and efficient projection operations on distributed machines. Experiments on real-world data show that our proposed LP solver, ECLIPSE, can solve problems with $10^{12}$ decision variables – well beyond the capabilities of current solvers.
APA
Basu, K., Ghoting, A., Mazumder, R. & Pan, Y.. (2020). ECLIPSE: An Extreme-Scale Linear Program Solver for Web-Applications. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:704-714 Available from https://proceedings.mlr.press/v119/basu20a.html.

Related Material