Abstract
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