  This paper introduces the design and implementation of two parallel dual
simplex solvers for general large scale sparse linear programming problems. One
approach, called PAMI, extends a relatively unknown pivoting strategy called
suboptimization and exploits parallelism across multiple iterations. The other,
called SIP, exploits purely single iteration parallelism by overlapping
computational components when possible. Computational results show that the
performance of PAMI is superior to that of the leading open-source simplex
solver, and that SIP complements PAMI in achieving speedup when PAMI results in
slowdown. One of the authors has implemented the techniques underlying PAMI
within the FICO Xpress simplex solver and this paper presents computational
results demonstrating their value. This performance increase is sufficiently
valuable for the achievement to be used as the basis of promotional material by
FICO. In developing the first parallel revised simplex solver of general
utility and commercial importance, this work represents a significant
achievement in computational optimization.
