The simplex method is frequently the most efficient method of solving linear programming (LP) problems. This paper reviews
previous attempts to parallelise the simplex method in relation to efficient serial simplex techniques and the nature of practical
LP problems. For the major challenge of solving general large sparse LP problems, there has been no parallelisation of the
simplex method that offers significantly improved performance over a good serial implementation. However, there has been some
success in developing parallel solvers for LPs that are dense or have particular structural properties. As an outcome of the
review, this paper identifies scope for future work towards the goal of developing parallel implementations of the simplex
method that are of practical value.
Keywords Linear programming - Simplex method - Sparse - Parallel computing
Mathematics Subject Classification (2000) 90C05