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.
Author: | Timo BertholdORCiD, Gregor HendelORCiD |
---|---|
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: | https://doi.org/10.1007/s10732-014-9271-0 |