论文标题
更快的稀疏maxcut和Qubo问题的解决方案
Faster exact solution of sparse MaxCut and QUBO problems
论文作者
论文摘要
最大切割问题是组合优化的基本问题之一。随着量子计算机的出现，近年来，最大切割和等效的二进制二进制优化问题都引起了很大的兴趣。 本文旨在通过在数字计算机上使用数学编程技术来精确解决这两个问题的精确解决方案。主要重点在于稀疏的问题实例，尽管也可以解决密集的问题。我们增强了几种算法组件，例如还原技术和切皮平面分离算法，并将它们结合在精确的分支和切割求解器中。此外，我们提供并行实现。新的求解器显示出用于稀疏麦克图克特和QUBO实例的现有最新软件。此外，我们在第七DIMAC挑战和QPLIB的几个实例中提高了最著名的界限，并将其中一些（首次）解决了最佳性。
The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems -- by using mathematical programming techniques on digital computers. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse MaxCut and QUBO instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.
