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

Speaker:

Kinjal Basu, staff applied researcher LinkedIn

 

Description:

 

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 talk, we describe 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 a trillion decision variables – well beyond the capabilities of current solvers.
 

Computational Mathematics and Statistics