Edinburgh Research Archive logo

Edinburgh Research Archive

University of Edinburgh homecrest
View Item 
  •   ERA Home
  • Mathematics, School of
  • Mathematics thesis and dissertation collection
  • View Item
  •   ERA Home
  • Mathematics, School of
  • Mathematics thesis and dissertation collection
  • View Item
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.

Presolve, crash and software engineering for HiGHS

View/Open
GalabovaI_2022.pdf (838.0Kb)
Date
18/01/2023
Author
Galabova, Ivet
Metadata
Show full item record
Abstract
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.
URI
https://hdl.handle.net/1842/39725

http://dx.doi.org/10.7488/era/2974
Collections
  • Mathematics thesis and dissertation collection

Library & University Collections HomeUniversity of Edinburgh Information Services Home
Privacy & Cookies | Takedown Policy | Accessibility | Contact
Privacy & Cookies
Takedown Policy
Accessibility
Contact
feed RSS Feeds

RSS Feed not available for this page

 

 

All of ERACommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsPublication TypeSponsorSupervisorsThis CollectionBy Issue DateAuthorsTitlesSubjectsPublication TypeSponsorSupervisors
LoginRegister

Library & University Collections HomeUniversity of Edinburgh Information Services Home
Privacy & Cookies | Takedown Policy | Accessibility | Contact
Privacy & Cookies
Takedown Policy
Accessibility
Contact
feed RSS Feeds

RSS Feed not available for this page