Tuesday, 15:15 - 15:40 h, Room: H 2013


Timo Berthold
Measuring the impact of primal heuristics


In modern MIP-solvers like the branch-cut-and-price-framework SCIP, primal heuristics play a major role in finding and improving feasible solutions at the early steps of the solution process.
However, classical performance measures for MIP such as time to optimality or number of branch-and-bound nodes reflect the impact of primal heuristics on the overall solving process rather badly. Reasons for this are that they typically depend on the convergence of the dual bound and that they only consider instances which can actually be solved within a given time limit.
In this talk, we discuss the question of how the quality of a primal heuristic should be evaluated and introduce a new performance measure, the "primal integral''. It depends on the quality of solutions found during the solving process as well as on the point in time when they are found. Thereby, it assesses the impact of primal heuristics on the ability to find feasible solutions of good quality, in particular early during search.
Finally, we discuss computational results for different classes of primal heuristics that are implemented in SCIP.


Talk 1 of the invited session Tue.3.H 2013
"Advances in mixed integer programming" [...]
Cluster 11
"Integer & mixed-integer programming" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.