Exploiting Solving Phases for Mixed-Integer Programs

Please always quote using this URN: urn:nbn:de:0297-zib-57098
  • Modern MIP solving software incorporates dozens of auxiliary algorithmic components for supporting the branch-and-bound search in finding and improving solutions and in strengthening the relaxation. Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process. We propose an adaptive solver behavior that dynamically reacts on transitions between the three typical phases of a MIP solving process: 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 demonstrate the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide heuristic alternatives to make use of the concept in practice.

Download full text files

Export metadata

  • Export Bibtex
Metadaten
Author:Gregor Hendel
Document Type:ZIB-Report
Tag:Branch-and-Bound, Mixed-Integer Programming
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Date of first Publication:2015/12/21
Series (Serial Number):ZIB-Report (15-64)
ISSN:1438-0064
Published in:Appeared in: Operations Research Proceedings 2015
DOI:http://dx.doi.org/10.1007/978-3-319-42902-1_1

$Rev: 13581 $