Parallelizing the dual revised simplex method

By Huangfu Qi, J. Hall. Mathematical Programming Computation, 2015

489 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/fd65174d9bda94906e7e4d1c6b94b02ba7b4af20

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

JuMP 1.0: recent improvements to a modeling language for mathematical optimization (2022, methodology): “For example, we can call the Highs_scaleCol function of HiGHS’s [8]”