Parallel Distributed-Memory Simplex for Large-Scale Stochastic LP Problems

Miles Lubin
Seminar

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.