12/9/2021: A systematic evaluation of heuristics for Max-Cut and QUBO, Swati Gupta, Georgia Institute of Technology

Speaker/presenter: Swati Gupta

Presentation Description:

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 implemented and released as open-source a code-base of 10 Max-Cut and 27 QUBO heuristics. We performed heuristic evaluation using cloud computing (on Amazon EC2) on an expanded library of heterogenous problem 3,296 instances (constructed using various graph libraries, random graph generators, and probabilities edge weights). This large-scale evaluation provided important insights 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 used machine learning to predict which heuristic will work best on a previously unseen problem instance, a key question facing practitioners.

During the talk, we discussed various details such as (1) definition of “coverage” of properties by instances in the expanded library, (2) selection of running time for each heuristic, (3) “fast” computation of features for each graph instance, (4) memory requirements for EC2 and variability of resources available on the core, (5) extrapolation of results for parallel runs of a few heuristics, as well as (6) the search for interesting instances (segue into the search for “quantum advantage”) and known values of optimal Max-Cut for the expanded instance library.

References:

[1] Iain Dunning, Swati Gupta, and John Silberholz. “What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO.” INFORMS Journal on Computing 30.3 (2018): 608-624.