201. Parallelizing the dual revised simplex method
- Author
-
J. A. J. Hall and Qi Huangfu
- Subjects
Speedup ,Linear programming ,Computer science ,65Y05 Parallel numerical computation ,0211 other engineering and technologies ,010103 numerical & computational mathematics ,02 engineering and technology ,Parallel computing ,90C05 Linear programming ,01 natural sciences ,Theoretical Computer Science ,90C06 Large-scale problems in mathematical programming ,FOS: Mathematics ,0101 mathematics ,Mathematics - Optimization and Control ,021103 operations research ,Simplex ,Computer Science - Numerical Analysis ,90C05, 90C06, 65K05 ,Numerical Analysis (math.NA) ,DUAL (cognitive architecture) ,Solver ,Revised simplex method ,Optimization and Control (math.OC) ,Theory of computation ,Parallelism (grammar) ,Software - Abstract
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., Comment: 27 pages
- Published
- 2017