Digital Annealer for quadratic unconstrained binary optimization: a comparative performance analysis

Understand

Digital Annealer (DA) is a computer architecture designed for tackling combinatorial optimization problems formulated as quadratic unconstrained binary optimization (QUBO) models.

• In this paper, we present the results of an extensive computational study to evaluate the performance of DA in a systematic way in comparison to multiple state-of-the-art solvers for different problem classes.
• We examine pure QUBO models, as well as QUBO reformulations of three constrained problems, namely quadratic assignment, quadratic cycle partition, and selective graph coloring, with the last two being new applications for DA.
• For the selective graph coloring problem, we also present a size reduction heuristic that significantly increases the number of eligible instances for DA.