Measuring the impact of primal heuristics
Please always quote using this URN: urn:nbn:de:0297-zib-17887
- In modern MIP solvers, primal heuristics play a major role in finding and improving feasible solutions early in the solution process. However, classical performance measures such as time to optimality or number of branch-and-bound nodes reflect the impact of primal heuristics on the overall solving process badly. This article discusses the question of how to evaluate the effect of primal heuristics. Therefore, we introduce a new performance measure, the "primal integral" which depends on the quality of solutions found during the solving process as well as on the points in time when they are found. Our computational results reveal that heuristics improve the performance of MIP solvers in terms of the primal bound by around 80%. Further, we compare five state-of-the-art MIP solvers w.r.t. the newly proposed measure.
Author: | Timo BertholdORCiD |
---|---|
Document Type: | ZIB-Report |
Tag: | mixed integer programming; performance measure; primal heuristic |
MSC-Classification: | 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/03/27 |
Series (Serial Number): | ZIB-Report (13-17) |
ISSN: | 1438-0064 |
Published in: | Appeared in: Operations Research Letters, vol. 41 no. 6 (2013), pp. 611-614 |
DOI: | https://doi.org/10.1016/j.orl.2013.08.007 |
Licence (German): | Creative Commons - Namensnennung-Keine Bearbeitung |