Parallelisation of the revised simplex method for general large scale LP problems

Contributed talk at Matrices in Statistics and Optimization: 18th October 2004

J. A. J. Hall


Despite its value in both the academic and commercial worlds, there has been no parallelisation of the revised simplex method that offers significantly improved performance over a good serial implementation for general large scale LP problems. A review of past approaches to parallelising the simplex method generally finds them to be either hopelessly inefficient or of no value for general problems. However, encouraging ideas are identified, pointing the way to future developments in this area. In particular, the parallel revised simplex scheme SYNPLEX is introduced. Preliminary results using an implementation in OpenMP on a Sun Fire E15k indicate that careful data distribution should lead to worthwhile speed-up.

Compressed Postscript
G-Zipped Postscript

Note that the postscript version is of finer resolution.

Last modified: