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.