Three high performance simplex solvers

Public lecture, Tokyo, 14 August 2017

Julian Hall

Abstract

This talk gives an overview of the computational features of three high performance implementations of the revised simplex method for solving large scale sparse linear programming (LP) problems. The first (EMSOL) was developed during relatively early work on parallelising the revised simplex method, but also yielded an important serial technique. The second (PIPS-S) was developed in collaboration with researchers at Argonne, and solves stochastic MIP relaxations in parallel. The third (h2gmp) was also written to study parallelism, and its underlying techniques will be introduced. Each solver has an associated article which won a best paper award in Computational Optimization and Applications. A particular crashing technique which leads to significantly improved solution time for certain classes of problem will also be presented. Final observations point the way to the use of h2gmp as a major open source linear optimization resource.

Slides:

PDF	Tokyo17.pdf

Papers:

• Parallelizing the dual revised simplex method
  Q. Huangfu and J. A. J. Hall
  Technical Report ERGO-14-011
  Accepted for publication in Mathematical Programming Computation

• Novel update techniques for the revised simplex method
  Q. Huangfu and J. A. J. Hall
  Technical Report ERGO-13-001
  Computational Optimization and Applications 60(3), 587-608, 2015. DOI: 10.1007/s10589-014-9689-1
  Awarded the prize for the best paper of 2015 in Computational Optimization and Applications

• Parallel distributed-memory simplex for large-scale stochastic LP problems
  M. Lubin, J. A. J. Hall, C. G. Petra and M. Anitescu
  Technical Report ERGO-12-005
  Computational Optimization and Applications 55(3), 571-596, 2013. DOI: 10.1007/s10589-013-9542-y
  Awarded the COIN-OR INFORMS 2013 Cup on 7 October 2013
  Awarded the prize for the best paper of 2013 in Computational Optimization and Applications

• Hyper-sparsity in the revised simplex method and how to exploit it
  J. A. J. Hall and K. I. M. McKinnon
  Hyper-sparsity October 2002
  Computational Optimization and Applications 32(3), 259-283, 2005. DOI: 10.1007/s10589-005-4802-0
  Awarded the prize for the best paper of 2005 in Computational Optimization and Applications