Building an iterative heuristic solver for a quantum annealer
Building an iterative heuristic solver for a quantum annealer
复制标题
DOI：
10.1007/s10589-016-9844-y
复制
发表时间：
2015-07
影响因子：
2.2
通讯作者：
G. Rosenberg;Mohammadreza Vazifeh;Brad D. Woods;E. Haber
中科院分区：
文献类型：
--
作者：
G. Rosenberg;Mohammadreza Vazifeh;Brad D. Woods;E. Haber
量子退火器启发式地最小化二次无约束二元优化（QUBO）问题，但在其可以处理的问题的大小和密度方面受到物理硬件的限制。我们开发了一个元启发式求解器，它利用D-Wave Systems的量子退火器（或任何其他QUBO问题优化器）通过迭代求解子问题来解决更大或更密集的问题，同时保持其余变量不变。我们提出了我们的算法，几个变种，和优化的标准QUBO问题的实例，从OR库的大小为500和2500，以及大小为3000-7000的Palubeckis实例的结果。对于实际使用的求解器，我们显示的时间依赖于最佳的解决方案所需的差距，以最好的解决方案。此外，我们研究的依赖性的差距和时间的最佳解决方案的大小的问题解决的底层优化。我们的结果是通过模拟获得的，使用禁忌1-opt求解器，由于所需的运行数量巨大，量子退火时间有限。
A quantum annealer heuristically minimizes quadratic unconstrained binary optimization (QUBO) problems, but is limited by the physical hardware in the size and density of the problems it can handle. We have developed a meta-heuristic solver that utilizes D-Wave Systems’ quantum annealer (or any other QUBO problem optimizer) to solve larger or denser problems, by iteratively solving subproblems, while keeping the rest of the variables fixed. We present our algorithm, several variants, and the results for the optimization of standard QUBO problem instances from OR-Library of sizes 500 and 2500 as well as the Palubeckis instances of sizes 3000–7000. For practical use of the solver, we show the dependence of the time to best solution on the desired gap to the best known solution. In addition, we study the dependence of the gap and the time to best solution on the size of the problems solved by the underlying optimizer. Our results were obtained by simulation, using a tabu 1-opt solver, due to the huge number of runs required and limited quantum annealer time availability.