A high performance dual revised simplex solver

Contributed talk at the 9th International Conference on Parallel Processing and Applied Mathematics Conference: 13th September 2011

J. A. J. Hall and Q. Huangfu


When solving families of related linear programming (LP) problems and many classes of single LP problems, the simplex method is the preferred computational technique. Hitherto there has been no efficient parallel implementation of the simplex method that gives good speed-up on general, large sparse LP problems. This paper presents a variant of the dual simplex method and a prototype parallelisation scheme. The resulting implementation, \ParISS, is efficient when run in serial and offers modest speed-up for a range of LP test problems.

PDF PPAM11.pdf