What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO

Iain Dunning (), Swati Gupta () and John Silberholz ()
Additional contact information
Iain Dunning: DeepMind, London N1C 4AG, United Kingdom
Swati Gupta: Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
John Silberholz: Ross School of Business, University of Michigan, Ann Arbor, Michigan 48109

INFORMS Journal on Computing, 2018, vol. 30, issue 3, 608-624

Abstract: Though empirical testing is broadly used to evaluate heuristics, there are shortcomings with how it is often 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 14% compare heuristics with identical termination criteria, and most experiments are performed with an artificial, homogeneous set of problem instances. To address these limitations, we implement and release as open-source a code-base of 10 Max-Cut and 27 QUBO heuristics. We perform heuristic evaluation using cloud computing on a library of 3,296 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.

Keywords: computational testing; reproducible research; heuristics; quadratic unconstrained binary optimization; Max-Cut; hyper-heuristics; test bed; interpretable machine learning (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0798 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:3:p:608-624

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().