An open-source high performance dual simplex solver

Contributed talk at SIAM Conference on Optimization, 22-25 May 2017

Julian Hall, Qi Huangfu and Ivet Galabova

Abstract

This talk presents the techniques underlying hsol, an open-source high performance dual simplex solver, as well as observations on the effectiveness of its presolve, advanced basis crash and dual edge weight pricing strategies. Specifically, an insight will be given into three features. Firstly, the solver's two novel update procedures [described in an article awarded the prize for the best paper of 2015 in Computational Optimization and Applications]. Secondly, its exploitation of task and data parallelism via suboptimization and, thirdly, its advanced basis crash. Historically, it has not been considered worthwhile to start the dual simplex method from an advanced basis following presolve and crash, but this talk will present results demonstrating its effectiveness for important classes of LP problems.

Slides:

PDF	SIOPT17.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

• 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