A distributed parallel dual revised simplex solver for large scale stochastic MIP problems

Invited talk at the Computational Linear Algebra and Optimization for the Digital Economy Workshop, ICMS, 1st November 2013.

J. A. J. Hall


When solving MIP problems efficiently using branch-and-bourd, the dual revised simplex method is generally used to solve the LP subproblems. Although parallel efficiency using the revised simplex method has not been achieved for general large sparse LP problems, this talk will show how the particular structure of stochastic LP problems gives scope for efficient data parallelism. Issues relating to algorithmic design and data distribution will be discussed. Results obtained on a large cluster and supercomputer using a distributed-memory implementation are presented for stochastic LP problems with up to 108 variables and constraints. These achieve parallel efficincy when using up to 128 cores and run up to 100 times faster than the leading open-source serial solver.