Fast approximate solution of linear programming problems

Lead Research Organisation: University of Edinburgh
Department Name: Sch of Mathematics

Abstract

The aim of this project is to develop and implement novel techniques preprocessing linear programming (LP) problems prior to application of the simplex method. The student will study existing "presolve" rules for the reduction of LP problems via the elimination of variables and constraints and develop efficient techniques for implementing them, as well as possibly identifying new presolve rules. Within the open source simplex solver Clp, there exists an undocumented and unpublished technique for obtaining an approximate solution of LP problems. This is known as the "Idiot crash", and is known to be effective for a limited class of LP problems. After studying and disseminating this technique, the student will develop novel algorithms that address the limitations of the Idiot crash in order to extend its applicability to a wider class of LP problems. The student's work will be developed in the context of the open source solver HiGHS, and can be expected to have an impact on commercial linear optimization software.

Publications

10 25 50

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/N509644/1 01/10/2016 30/09/2021
2304302 Studentship EP/N509644/1 01/10/2016 31/08/2021 Ivet Lyubomirova Galabova