### 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*

##### Abstract

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*