论文标题
通过QUBO和数字退火进行图形聚类
Graph Clustering Via QUBO and Digital Annealing
论文作者
论文摘要
本文凭经验研究了使用新颖的专用计算机硬件来解决已知的硬问题，图形聚类的计算成本。我们将图表聚类问题表示为群集内距离或异异性最小化问题。我们将台词作为二次无约束的二进制优化问题提出，并采用新颖的计算机架构来获得数值解决方案。我们的起点是文献的聚类表述。然后将此公式转换为二次无约束的二进制优化公式。最后，我们使用新颖的专用计算机架构来获取数值解决方案。为了进行基准测试，我们还将计算性能与使用常规硬件运行的商业求解器Gurobi获得的计算性能进行比较。我们的初始结果表明，专用的硬件为商业求解器提供了等效的解决方案，但在所需的时间很小的一小部分。
This article empirically examines the computational cost of solving a known hard problem, graph clustering, using novel purpose-built computer hardware. We express the graph clustering problem as an intra-cluster distance or dissimilarity minimization problem. We formulate our poblem as a quadratic unconstrained binary optimization problem and employ a novel computer architecture to obtain a numerical solution. Our starting point is a clustering formulation from the literature. This formulation is then converted to a quadratic unconstrained binary optimization formulation. Finally, we use a novel purpose-built computer architecture to obtain numerical solutions. For benchmarking purposes, we also compare computational performances to those obtained using a commercial solver, Gurobi, running on conventional hardware. Our initial results indicate the purpose-built hardware provides equivalent solutions to the commercial solver, but in a very small fraction of the time required.
