A high performance dual revised simplex solver

Technical Report ERGO-11-007

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.

Key words: Linear programming, Dual revised simplex method, Parallel algorithms

PDF ERGO-11-007.pdf
Related Publications

Submitted to PPAM 2011: 9th International Conference on Parallel Processing and Applied Mathematics (2011)
PPAM 2011, Part I, Springer Lecture Notes in Computer Science 7203, 143-151, 2012