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.

Download full text files

Export metadata

  • Export Bibtex
Metadaten
Author:Timo Berthold
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:http://dx.doi.org/10.1016/j.orl.2013.08.007
Licence (German):License LogoCreative Commons - Namensnennung-Keine Bearbeitung

$Rev: 13581 $