Optimization Online


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

Miles Lubin (mlubin***at***mcs.anl.gov)
J. A. Julian Hall (j.a.j.hall***at***ed.ac.uk)
Cosmin G. Petra (petra***at***mcs.anl.gov)
Mihai Anitescu (anitescu***at***mcs.anl.gov)

Abstract: We present a parallelization of the revised simplex method for large extensive forms of two-stage stochastic linear programming (LP) problems. These problems have been considered too large to solve with the simplex method; 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 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 the largest-scale parallel sparsity-exploiting revised simplex implementation that has been developed to date and the first truly distributed solver. It is built on novel analysis of the linear algebra for dual block-angular LP problems when solved by using the revised simplex method and a novel parallel scheme for applying product-form updates.

Keywords: simplex method, parallel computing, stochastic optimization, block-angular

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 3: Stochastic Programming

Citation: Computational Optimization and Applications, in press

Download: [PDF]

Entry Submitted: 04/17/2012
Entry Accepted: 04/17/2012
Entry Last Modified: 02/09/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society