Parallel distributed-memory simplex for large-scale stochastic LP problems
Contributed talk at CSC14: The Sixth SIAM Workshop on Combinatorial Scientific Computing, Lyon, 21st July 2014.
J. A. J. Hall
Abstract
generally solved using the dual revised simplex method. Despite
its potential value, there has been relatively little research into
the development of implementations of the revised simplex method which
exploit parallel computing environments. Hitherto these efforts have
met with very limited success, in particular for general large sparse
LP problems. This talk will discuss three recent approaches. The first
two exploit data and task pallelism when solving general LP problems
and achieve meaningful performance improvement relative to Clp, the
leading open-source serial simplex solver. The third approach exploits
the inherent data parallelism resulting from the structure of
stochastic LP problems. 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.
Slides:
Paper:
Parallel distributed-memory simplex for large-scale stochastic LP problems
M. Lubin, J. A. J. Hall, C. G. Petra and M. Anitescu
Technical Report ERGO-12-005.
Computational
Optimization and Applications 55(3), 571-596,
2013. DOI: 10.1007/s10589-013-9542-y