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

Contributed talk at APMOD 04: 21st June 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 and preliminary results are given.

Compressed Postscript
G-Zipped Postscript

Note that the postscript version is of finer resolution.

Last modified: