LANS Informal Seminar: Miles Lubin

Seminar Title: Parallel distributed-memory simplex for large-scale stochastic LP problems
Speaker: Miles Lubin, Predoc, MCS

Date/Time: 2012-04-11 15:00
Location: Building 240, 4301

Description:
In this talk, we will present our current work on a novel parallelization of the revised simplex method for large deterministic-equivalent forms of stochastic linear-programming (LP) problems. These problems have been considered too large to solve by using the simplex method, and instead, decomposition approaches based on row generation or, more recently, interior-point methods are generally used. However, these approaches do not provide optimal basic solutions, which allow for efficient hot-starts and can provide important sensitivity information. Our approach exploits the dual block-angular structure of these problems inside the linear algebra of the revised simplex method in a data-parallel manner suitable for high-performance distributed-memory clusters or supercomputers. While our focus is on stochastic LPs, the work is applicable to all problems with a dual block-angular structure. Our implementation is competitive in serial with highly-efficient sparsity-exploiting simplex codes and achieves significant relative speed-ups when run in parallel. Additionally, very large problems with hundreds of millions of variables have been successfully solved to optimal bases.