Parallelizing the dual revised simplex method

Mathematical Programming Computation, 10 (1), 119-142, 2018. DOI: J.A.J. Hall

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. In developing the first parallel revised simplex solver of general utility, this work represents a significant achievement in computational optimization.

Key words: Linear programming; Revised simplex method; Parallel computing

Awarded the prize for the best paper of 2018 in Mathematical Programming Computation


Text
Published article: PDF
Test problems:
With the exception of dcp2, the test problems used in this paper are drawn from a variety of public domain test sets. For convenience, they are collected in HuHa13_TestSet.zip (90MB)

Related Publications
ERGO-11-007
ERGO-13-001

History:
Mathematical Programming Computation, 10 (1), 119-142, 2018. DOI: 10.1007/s12532-017-0130-5 and goo.gl/bzXqZX
Original technical report: ERGO-14-011
Also available via arXiv