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

  • Export Bibtex
Author:Gregor Hendel
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
Licence (German):License LogoCreative Commons - Namensnennung-Keine Bearbeitung

$Rev: 13581 $