### Julian Hall (University of Edinburgh)

#### Solving very sparse LP problems with the revised simplex method

*Wednesday 2 June 1999 at 15.30, JCMB 6324*

##### Abstract

When solving large sparse linear programming (LP) problems, a typical
implementation of the revised simplex method with a sparse
factorisation of the basis matrix avoids the prohibitive cost of the
standard simplex method or the revised simplex method with the
explicit inverse of the basis matrix. In significant classes of LP
problems, in particular those with a near or pure network structure,
there is little or no fill-in in the factors of the basis matrix. For
such very sparse problems, this paper illustrates how the
computational cost of a commercial-quality implementation of the
revised simplex method is dominated by operations involving zero
values. Techniques by which this hyper-sparsity may be exploited are
described. It is demonstrated that these techniques result in a
computational performance which is vastly superior to that of at least
one major commercial implementation of the revised simplex method. The
extent to which the performance approaches that of a dedicated network
LP solver is also examined.

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