Fast approximate solution of linear programming problems

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.