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.
Organisations
People |
ORCID iD |
Julian Hall (Primary Supervisor) | |
Ivet Galabova (Student) |
Studentship Projects
Project Reference | Relationship | Related To | Start | End | Student Name |
---|---|---|---|---|---|
EP/N509644/1 | 30/09/2016 | 29/09/2021 | |||
2304302 | Studentship | EP/N509644/1 | 31/08/2016 | 30/10/2021 | Ivet Galabova |