Parallel distributed-memory simplex for large-scale stochastic LP problems

We present a 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 using the simplex method, and instead, decomposition approaches based on Benders decomposition or, more recently, interior-point methods are generally used. However, these approaches do not provide optimal basic solutions, which allow for efficient hot-starts (e.g. in a branch-and-bound context) 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 this paper focuses 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 optimality. This is very much the largest scale parallel revised simplex implementation that has been developed and the first truly distributed solver. It is built on novel analysis of the linear algebra for dual block-angular LP problems when solved using the revised simplex method and a novel parallel scheme for applying product form updates.