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


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.