Hall, Julian

Gondzio, Jacek

Galabova, Ivet

2023-01-18T14:34:34Z

2023-01-18T14:34:34Z

2023-01-18

The efficient computational solution of linear optimization problems is generally enhanced significantly by using a "presolve" procedure to process the problem logically in order to reduce the dimension of the problem to be solved algorithmically. In the absence of other information about the optimal solution to the problem, it is often worth performing a cheap "crash" procedure to obtain a solution that is near-feasible and, ideally, near-optimal. When a problem has been presolved, it is essential to be able to deduce the original problem's optimal solution from the optimal solution of the presolved problem. This thesis provides an analysis of the Idiot crash algorithm (ICA) for linear programming (LP) problems, and techniques for primal and dual postsolve corresponding to established presolve techniques. It demonstrates that presolve yields significant performance enhancement for standard test problems, and identifies that use of the ICA enhances the solution process for a significant range of test problems. This is particularly so in the case of linearisations of quadratic assignment problems that are, otherwise, very challenging for standard methods of solution. The techniques are implemented in the HiGHS open-source software system. The use of modern techniques to create robust and efficient software system for HiGHS and its interfaces has been a critical feature of its success. Accordingly, this thesis sets out the philosophy and techniques of the software engineering underpinning HiGHS.

https://hdl.handle.net/1842/39725

http://dx.doi.org/10.7488/era/2974

en

The University of Edinburgh

HiGHS

Idiot crash algorithm

ICA

linear programming

LP

HiGHS open-source software system

Presolve, crash and software engineering for HiGHS

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy