Rounding and Propagation Heuristics for Mixed Integer Programming
Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-13255
- Primal heuristics are an important component of state-of-the-art codes for mixed integer programming. In this paper, we focus on primal heuristics that only employ computationally inexpensive procedures such as rounding and logical deductions (propagation). We give an overview of eight different approaches. To assess the impact of these primal heuristics on the ability to find feasible solutions, in particular early during search, we introduce a new performance measure, the primal integral. Computational experiments evaluate this and other measures on MIPLIB~2010 benchmark instances.
Verfasserangaben: | Tobias AchterbergORCiD, Timo BertholdORCiD, Gregor HendelORCiD |
---|---|
Dokumentart: | ZIB-Report |
Freies Schlagwort / Tag: | domain propagation; mixed integer programming; primal heuristic |
MSC-Klassifikation: | 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 | |
Datum der Erstveröffentlichung: | 14.07.2011 |
Schriftenreihe (Bandnummer): | ZIB-Report (11-29) |
ZIB-Reportnummer: | 11-29 |
Verlagspublikation: | Appeared in: Operations Research Proceedings 2011. Diethard Klatte et al. (eds.) Springer 2012, pp. 71-76 |
DOI: | https://doi.org/10.1007/978-3-642-29210-1_12 |