Miles Lubin (Argonne National Laboratory, USA)

Parallel distributed-memory simplex for large-scale stochastic LP problems
Joint work with Julian Hall.
Tuesday 26 June 2012 at 16.00, JCMB 6206


We will present our recent work on parallelizing the revised simplex method for solving large-scale linear programming problems (LPs) with dual block angular structure, motivated by stochastic programming models which arise in power grid control under uncertainty. In practice, sequences of LPs must be solved both in real-time control and in branch-and-bound algorithms; however, existing parallel decomposition procedures, those based on Benders decomposition and linear-algebra decomposition within interior-point methods, are known to be difficult to warm start. The simplex algorithm, on the other hand, can be effectively hot-started but is believed to be very difficult to parallelize. Our successful parallelization 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. 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 optimal bases. The implementation is built on novel analysis of the linear algebra for dual block-angular LP problems when solved by using the revised simplex method and on a novel parallel scheme for applying product-form updates.

Seminars by year

Current 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996