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

Contributed talk at the International Conference on Numerical Optimization and Numerical Linear Algebra 2005 (ICNLAO 2005): 9-10th August 2005

J. A. J. Hall

Abstract

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. Results obtained using a prototype implementation in OpenMP on a Sun Fire E15k indicate that careful data distribution should lead to worthwhile speed-up. The development of an advanced implementation incorporating sophisticated data and task distribution is ongoing.