Shift-and-Propagate

  • 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.

Export metadata

  • Export Bibtex
Metadaten
Author:Timo Berthold, Gregor Hendel
Document Type:Article
Parent Title (English):Journal of Heuristics
Volume:21
Issue:1
First Page:73
Last Page:106
Year of first publication:2014
Preprint:urn:nbn:de:0297-zib-17596
DOI:http://dx.doi.org/10.1007/s10732-014-9271-0

$Rev: 13581 $