Shift-And-Propagate

Please always quote using this URN: urn:nbn:de:0297-zib-17596
  • For mixed integer programming, recent years have seen a growing interest in the design of general purpose primal heuristics for use inside complete solvers. Many of these heuristics rely on an optimal LP solution. Finding this may itself take a significant amount of time. The presented paper addresses this issue by the introduction of the Shift-And-Propagate heuristic. Shift-And-Propagate is a pre-root primal heuristic that does not require a previously found LP solution. It applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement of existing rounding and propagation heuristics.

Download full text files

Export metadata

  • Export Bibtex
Metadaten
Author:Timo Berthold, Gregor Hendel
Document Type:ZIB-Report
Tag:domain propagation; mixed integer programming; primal heuristic; rounding
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C59 Approximation methods and heuristics
Date of first Publication:2013/01/04
Series (Serial Number):ZIB-Report (13-03)
ISSN:1438-0064
Published in:Appeared in: Journal of Heuristics 21 (2015) pp. 73-106
DOI:http://dx.doi.org/10.1007/s10732-014-9271-0

$Rev: 13581 $