What Works Best When? A Framework for Systematic Heuristic Evaluation
Iain Dunning, Swati Gupta, John Silberholz · 2015
Though empirical testing is broadly used to evaluate heuristics, there are major shortcomings with how it is applied in practice. In a systematic review of Max-Cut and Quadratic Unconstrained Binary Optimization (QUBO) heuristics papers, we found only 4% publish source code, only 10% compare heuristics with identical hardware and termination criteria, and most experiments are performed with an articial, homogeneous set of problem instances. To address these limitations, we rst propose a framework for reproducible heuristic evaluation based on large-scale open-source implementation, expanded sets of test instances, and evaluation with cloud computing. We give a proof of concept of the framework by testing 37 Max-Cut and QUBO heuristics across 3,298 problem instances. This large-scale evaluation provides insight into the types of problem instances for which each heuristic performs well or poorly. Because no single heuristic outperforms all others across all problem instances, we use machine learning to predict which heuristic will work best on a previously unseen problem instance, a key question facing practitioners. We hope our framework will be applied broadly to identify \what works best when among heuristics for a range of optimization problems.