Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. As many NP-hard problems can be reduced to QUBO problems, considerable research has gone into developing QUBO solvers running on various computing platforms such as quantum devices, ASICs, FPGAs, GPUs, and optical fibers. This paper presents a framework called Diverse Adaptive Bulk Search (DABS), which has the potential to find optimal solutions of many types of QUBO problems. Our DABS solver employs a genetic algorithm-based search algorithm featuring three diverse strategies: multiple search algorithms, multiple genetic operations, and multiple solution pools. During the execution of the solver, search algorithms and genetic operations that succeeded in finding good solutions are automatically selected to obtain better solutions. Moreover, search algorithms traverse between different solution pools to find good solutions. We have implemented our DABS solver to run on multiple GPUs. Experimental evaluations using eight NVIDIA A100 GPUs confirm that our DABS solver succeeds in finding optimal or potentially optimal solutions for three types of QUBO problems.
翻译:二次非约束二进制优化(QUBO)是一种组合优化问题,旨在寻找使由二进制变量构成的向量的二次公式的能量值最小化的最优二进制解向量。由于许多 NP 难问题可以归约为 QUBO 问题,因此已经进行了相当多的研究,以开发运行于各种计算平台(如量子设备、 ASIC、FPGA、GPU 和光导纤维)上的 QUBO 求解器。本文提出了一个名为 'Diverse Adaptive Bulk Search'(DABS)的框架,具有潜力用于发现许多类型的 QUBO 问题的最优解。我们的 DABS 求解器采用了基于遗传算法的搜索算法,具有三种不同的策略:多个搜索算法、多个遗传操作和多个解池。在求解器的执行过程中,自动选择成功找到好解的搜索算法和遗传操作以获得更好的解,且搜索算法在不同的解池之间进行遍历以找到好的解。我们已经实现了 DABS 求解器,以在多个 GPU 上运行。实验评估使用 8 个 NVIDIA A100 GPU,确认我们的 DABS 求解器能够成功地找到三种类型的 QUBO 问题的最优或潜在最优解。