论文标题
二次不受约束的二进制优化的数字退火器：比较性能分析
Digital Annealer for quadratic unconstrained binary optimization: a comparative performance analysis
论文作者
论文摘要
Digital Exealer（DA）是一种计算机体系结构，旨在解决作为二次无约束二进制优化（QUBO）模型的组合优化问题。在本文中，我们介绍了一项广泛的计算研究的结果，该研究与多个针对不同问题类别的最先进的求解器相比，以系统的方式评估DA的性能。我们检查了纯QUBO模型，以及三个受约束问题的QUBO重新印象，即二次分配，二次循环分区和选择性图形着色，最后两个是DA的新应用。对于选择性的图形着色问题，我们还提出了一个尺寸降低的启发式方法，可显着增加DA的合格实例数量。我们的实验结果表明，尽管处于开发阶段，但DA仍可以快速提供高质量的解决方案，在这方面，竞争对面的状态，尤其是在大型实例中。此外，与已建立的求解器相比，在其决策变量数量的范围内，DA的解决方案时间不受实例大小的增加的影响。这些发现表明，DA有可能成为解决组合优化问题的成功技术。
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. Our experimental results show that despite being in its development stage, DA can provide high-quality solutions quickly and in that regard rivals the state of the art, particularly for large instances. Moreover, as opposed to established solvers, within its limit on the number of decision variables, DA's solution times are not affected by the increase in instance size. These findings illustrate that DA has the potential to become a successful technology in tackling combinatorial optimization problems.
