Seminar Details:

LANS Informal Seminar
"Parallel distributed-memory simplex for large-scale stochastic LP problems"

DATE: April 11, 2012

TIME: 15:00:00 - 16:00:00
SPEAKER: Miles Lubin, Predoc, MCS
LOCATION: Building 240, 4301, Argonne National Laboratory

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.


 

Please send questions or suggestions to Krishna: snarayan at mcs.anl.gov.