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

### Kinjal Basu · Amol Ghoting · Rahul Mazumder · Yao Pan

Keywords: [ Large Scale Learning and Big Data ] [ Recommender Systems ] [ Other ] [ Optimization - Large Scale, Parallel and Distributed ]

[ Abstract ] [ Join Zoom
[
Abstract: Key problems arising in web applications (with millions of users and thousands of items) can be formulated as Linear Programs (LP) involving billions to trillions of decision variables and constraints. Despite the appeal of LP formulations, solving problems at these scales appears 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 lead to a 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 with computational guarantees. 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.