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:

PDF ZIB17.pdf

Papers: