论文标题
使用QUBO求解器进行基于置换的组合优化的混合框架
A Hybrid Framework Using a QUBO Solver For Permutation-Based Combinatorial Optimization
论文作者
论文摘要
在本文中，我们提出了一个混合框架，以使用高性能二进制二进制优化（QUBO）求解器有效地解决大规模置换的组合问题。为此，需要转换来将约束优化模型更改为涉及参数调整的不受约束模型。我们提出的技术来克服通常使用有限数量的QUBO求解器来克服挑战。首先，为了平滑能量景观，我们在不损害最优性的情况下减少了输入的幅度。我们提出了一种机器学习方法，以有效地调整参数，以有效地进行良好的性能。为了处理可能的不可行性，我们引入了多项式投影算法。最后，为了解决大规模的问题，我们引入了一种分裂和纠纷方法，该方法在小的子问题上反复称呼Qubo求解器。我们测试了对可证明的欧几里得旅行推销员（E-TSP）实例和流店问题（FSP）的方法。与最著名的方法相比，分别获得小于$ 10 \％$和$ 11 \％$的最佳差距。
In this paper, we propose a hybrid framework to solve large-scale permutation-based combinatorial problems effectively using a high-performance quadratic unconstrained binary optimization (QUBO) solver. To do so, transformations are required to change a constrained optimization model to an unconstrained model that involves parameter tuning. We propose techniques to overcome the challenges in using a QUBO solver that typically comes with limited numbers of bits. First, to smooth the energy landscape, we reduce the magnitudes of the input without compromising optimality. We propose a machine learning approach to tune the parameters for good performance effectively. To handle possible infeasibility, we introduce a polynomial-time projection algorithm. Finally, to solve large-scale problems, we introduce a divide-and-conquer approach that calls the QUBO solver repeatedly on small sub-problems. We tested our approach on provably hard Euclidean Traveling Salesman (E-TSP) instances and Flow Shop Problem (FSP). Optimality gap that is less than $10\%$ and $11\%$ are obtained respectively compared to the best-known approach.
