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

Miles Lubin, Julian Hall, Cosmin Petra, Mihai Anitescu

Research output: Contribution to journalArticlepeer-review

Abstract

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.
Original languageEnglish
Pages (from-to)571-596
Number of pages26
JournalComputational optimization and applications
Volume55
Issue number3
Early online date23 Feb 2013
DOIs
Publication statusPublished - 29 Jun 2013

Fingerprint Dive into the research topics of 'Parallel distributed-memory simplex for large-scale stochastic LP problems'. Together they form a unique fingerprint.

  • Best Paper Award

    Lubin, M. (Recipient), Hall, Julian (Recipient), Petra, C. (Recipient) & Anitescu, M. (Recipient), 2013

    Prize: Prize (including medals and awards)

  • COIN-OR INFORMS Cup

    Lubin, M. (Recipient), Hall, Julian (Recipient), Petra, C. (Recipient) & Anitescu, M. (Recipient), 2013

    Prize: Prize (including medals and awards)

Cite this