Towards a practical parallelisation of the simplex method

ParSimplex February 2005

J.A.J. Hall

The simplex method is frequently the most efficient method of solving general large sparse linear programming (LP) problems. Despite this, there has been no parallelisation of the simplex method that offers significantly improved performance over a good serial implementation of the revised simplex method. This paper reviews previous attempts to parallelising the simplex method and finds them to be, at worst, hopelessly inefficient and, at best, of insufficient value for general problems to be adopted practically. However, encouraging ideas are identified, pointing the way to worthwhile future developments in this area.

Key words: linear programming, simplex method, sparse, parallel computing

PDF ParSimplexFebruary2005.pdf
Related Publications
Technical Report MS 95-050b
Technical Report MS 96-012
ParSimplex April 2007

Submitted to Computational Management Science (February 2005).
Available from Optimization Online