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 calledsuboptimization and exploits parallelism across multiple iterations. The other,called SIP, exploits purely single iteration parallelism by overlappingcomputational components when possible. Computational results show that theperformance of PAMI is superior to that of the leading open-source simplexsolver, and that SIP complements PAMI in achieving speedup when PAMI results inslowdown. One of the authors has implemented the techniques underlying PAMIwithin the FICO Xpress simplex solver and this paper presents computationalresults demonstrating their value. This performance increase is sufficientlyvaluable for the achievement to be used as the basis of promotional material byFICO. In developing the first parallel revised simplex solver of generalutility and commercial importance, this work represents a significantachievement in computational optimization.
展开▼
