Three high performance simplex solvers

Seminar at Argonne National Laboratory 16 May 2017

Julian Hall and Ivet Galabova


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 (hsol) 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 hsol as a major open source linear optimization resource.


PDF Argonne17.pdf