Julian Hall (University of Edinburgh)

50 Years of the simplex method
Monday 5 May 1997 at 15.30, JCMB 5215


Linear programming (LP) is the most widely-used technique in mathematical modelling. The simplex method is the most reliable solution technique and remains the preferred choice when families of LP problems are to be solved. Following its invention by George Dantzig in 1947, the development of algorithmic refinements and computational techniques progressed steadily over the following 25 years. In the subsequent 25 years, although the efficiency of simplex software has continued to improve, there have been few significant algorithmic developments.

Following each new advance in computing technology, there are often significant developments in numerical methods for the major mathematical models. Indeed, awareness of the coming of the electronic computer motivated the invention of the simplex method itself. However, since the simplex method is viewed as being inherently sequential, there has been virtually no attempt to exploit the many developments in parallel computing.

This talk will chart the history of the simplex method, from Dantzig's original standard simplex method which is sufficiently elementary to be taught in first-year university courses such as our own AM1, through the development of algorithmic and computational techniques for solving large sparse problems, to the recent algorithmic developments of Hall and McKinnon which offer the prospect of finally exploiting the potential of parallel computers such as the Cray T3D.

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