István Maros (Imperial College)

Finding better starting bases for the simplex method
Wednesday 4 December 1996 at 15.30, JCMB 6324

Abstract

The performance of the revised sparse simplex (SSX) method or its variants for the solution of large scale linear programming (LP) problems can be considerably enhanced if an advanced starting basis is introduced instead of the traditional all logical initial basis. We consider two such procedures known as crash procedures to obtain advanced starting points for the SSX:

  1. We extend traditional crash procedures whereby triangularity of the basis is always maintained and take advantage of the problem characteristics; we apply additional criteria for determining the entering structural variables and their position in the basis.
  2. We allow the triangularity to be slightly "violated", and make some cheap pivot steps to find a better basis.

We present an analysis of issues followed by a description of the techniques. Computational experience is also reported.

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