Fast solution of LP problems
Zuse Institute Berlin, 10 October 2017
Julian Hall and Ivet Galabova
Abstract
This talk presents two techniques for the fast solution of linear programming (LP) problems: one traditional and one modern. The dual revised simplex method is generally used when families of related LP problems are solved, particularly in the context of branch-and-bound techniques for mixed-integer programming problems. This talk will describe three update techniques and the high performance dual revised simplex solver for which they were developed. The new open-source linear optimization package h2gmp, which has the dual revised simplex solver at its heart and includes an interface to SCIP, will also be introduced. The talk will conclude by presenting recent work on analysing the Idiot crash of Forrest which is implemented in Clp. In addition to its use as a valuable advanced basis crash for some LP problems, it will be seen to provide a very fast approximate solution method for an important class of LP problems. It will also be shown that the Idiot crash is a particular variant of the augmented Lagrangian method, pointing the way to improved methods for fast approximate solution of LP problems.
Slides:
ZIB17.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 ComputationNovel 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