High performance simplex solvers for linear programming problems
Technical talk: Google, Paris, 11 September 2015.
J. A. J. Hall
Abstract
The efficient solution of large sparse linear programming (LP) problems is essential, whether they be problems in their own right or sub-problems generated when solving discrete or decomposed linear optimization problems. The dual revised simplex method is frequently the preferred approach, particularly when solving families of related problems. This talk will explore the algorithmic and computational techniques by which the dual revised simplex method may be implemented efficiently, both in serial and in parallel.
Exploiting hyper-sparsity in the numerical linear algebra of the revised simplex method is important for the efficient serial solution of many practical problems. This phenomenon will be introduced and techniques for its exploitation and promotion will be discussed. This talk will also discuss three relatively recent approaches to exploiting parallel computing environments. The first two exploit data and task parallelism when solving general LP problems and achieve meaningful performance improvement relative to Clp, the leading open-source serial simplex solver. The third approach exploits the inherent data parallelism resulting from the structure of stochastic LP problems. These techniques achieve parallel efficiency when using up to 128 cores and run up to 100 times faster than Clp. Results will be presented for stochastic LP problems with up to 108 variables and constraints.
Slides: