This paper introduces the design and implementation of two parallel dualsimplex solvers for general large scale sparse linear programming problems. Oneapproach, called PAMI, extends a relatively unknown pivoting strategy called suboptimizationand exploits parallelism across multiple iterations. The other, called SIP,exploits purely single iteration parallelism by overlapping computational componentswhen possible. Computational results show that the performance of PAMI is superiorto that of the leading open-source simplex solver, and that SIP complements PAMIin achieving speedup when PAMI results in slowdown. One of the authors has implementedthe techniques underlying PAMI within the FICO Xpress simplex solver andthis paper presents computational results demonstrating their value. In developing thefirst parallel revised simplex solver of general utility, this work represents a significantachievement in computational optimization.
展开▼
