@article{BertholdHendel, author = {Berthold, Timo and Hendel, Gregor}, title = {Shift-and-Propagate}, series = {Journal of Heuristics}, volume = {21}, journal = {Journal of Heuristics}, number = {1}, doi = {10.1007/s10732-014-9271-0}, pages = {73 -- 106}, abstract = {In recent years, there has been a growing interest in the design of general purpose primal heuristics for use inside complete mixed integer programming solvers. Many of these heuristics rely on an optimal LP solution, which may take a significant amount of time to find. In this paper, we address this issue by introducing a pre-root primal heuristic that does not require a previously found LP solution. This heuristic, named Shift-and-Propagate , applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement to existing rounding and propagation heuristics.}, language = {en} } @misc{Hendel, type = {Master Thesis}, author = {Hendel, Gregor}, title = {Empirical Analysis of Solving Phases in Mixed Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54270}, pages = {159}, abstract = {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.}, language = {en} }