Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Empirical Analysis of Solving Phases in Mixed Integer Programming

Please always quote using this URN: urn:nbn:de:0297-zib-54270
  • Modern solving software for mixed-integer programming (MIP) incorporates numerous algorithmic components whose behavior is controlled by user parameter choices, and whose usefulness dramatically varies depending on the progress of the solving process. In this thesis, our aim is to construct a phase-based solver that dynamically reacts on phase transitions with an appropriate change of its component behavior. Therefore, we decompose the branch-and-bound solving process into three distinct phases: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP we construct a phase-based solver to make use of the phase concept in two steps: First, we identify promising components for every solving phase individually and show that their combination is beneficial on a test bed of practical MIP instances. We then present and evaluate three heuristic criteria to make use of the phase-based solver in practice, where it is infeasible to distinguish between the last two phases before the termination of the solving process.

Download full text files

Export metadata

Metadaten
Author:Gregor HendelORCiD
Document Type:Master's Thesis
Tag:branch-and-cut; mixed-integer programming
Granting Institution:Technische Universität Berlin
Advisor:Thorsten Koch, Timo Berthold
Date of final exam:2014/08/27
Year of first publication:2014
Page Number:159
Licence (German):License LogoCreative Commons - Namensnennung-Keine Bearbeitung
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.