6160
2016
eng
reportzib
1
--
2016-12-30
--
The Three Phases of MIP Solving
Modern MIP solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound.
Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three different phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behavior of the MIP solver SCIP at the predicted phase transition points.
1438-0064
urn:nbn:de:0297-zib-61607
10.1080/10556788.2017.1392519
Optimization Methods and Software
Timo Berthold
Gregor Hendel
Gregor Hendel
Thorsten Koch
ZIB-Report
16-78
eng
uncontrolled
optimization software
eng
uncontrolled
mixed-integer programming
eng
uncontrolled
branch-and-bound
eng
uncontrolled
adaptive search behavior
eng
uncontrolled
optimality prediction
Mathematics of Computing
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Berthold, Timo
Hendel, Gregor
Koch, Thorsten
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6160/zib-paper.pdf