5709
2015
eng
reportzib
0
--
2015-12-21
--
Exploiting Solving Phases for Mixed-Integer Programs
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.
1438-0064
urn:nbn:de:0297-zib-57098
10.1007/978-3-319-42902-1_1
Appeared in: Operations Research Proceedings 2015
Gregor Hendel
Gregor Hendel
ZIB-Report
15-64
eng
uncontrolled
Branch-and-Bound, Mixed-Integer Programming
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Hendel, Gregor
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5709/Hendel_ExploitingSolvingPhases.pdf