Heuristic solvers of the Quadratic Unconstrained Binary Optimization (QUBO) problems have been rapidly studied because of their potentialities to solve a wide range of com-binatorial optimization problems in a unified manner. QUBO solvers, however, face a limitation in the numbers of variables. To overcome this limitation, we reformulate QUBO as a maximum weight induced subgraph problem (MISG) and propose a graph-theoretic approach for solving MISG. It is a problem to find an induced subgraph with the maximum total weight for a given edge-weighted undirected graph. Naive local search that updates only one vertex at a time requires many iterations to obtain good solutions for large-scale problems. To accelerate it, we introduce a new technique to update multiple vertices that can improve the solution at the same time. We have implemented a MISG solver based on our algorithm on NVIDIA A100 GPUs, where flip operations are parallelized with GPU multithreaded computing. Our solver is scalable and supports up to 230(1G) variables. Our results show that our algorithm outperforms the Gurobi optimizer in terms of solution qualities and the execution time.
Heuristic solvers of the Quadratic Unconstrained Binary Optimization (QUBO) problems have been rapidly studied because of their potentialities to solve a wide range of com-binatorial optimization problems in a unified manner. QUBO solvers, however, face a limitation in the numbers of variables. To overcome this limitation, we reformulate QUBO as a maximum weight induced subgraph problem (MISG) and propose a graph-theoretic approach for solving MISG. It is a problem to find an induced subgraph with the maximum total weight for a given edge-weighted undirected graph. Naive local search that updates only one vertex at a time requires many iterations to obtain good solutions for large-scale problems. To accelerate it, we introduce a new technique to update multiple vertices that can improve the solution at the same time. We have implemented a MISG solver based on our algorithm on NVIDIA A100 GPUs, where flip operations are parallelized with GPU multithreaded computing. Our solver is scalable and supports up to 230(1G) variables. Our results show that our algorithm outperforms the Gurobi optimizer in terms of solution qualities and the execution time.
The quadratic unconstrained binary optimization (QUBO) is recently gathering attention in conjunction with quantum annealing (QA), since it is equivalent to finding the ground state of an Ising model. Due to the limitation of current QA systems, classical computers may outperform them. Researchers have thus been proposed to solve QUBO on FPGAs, GPUs, and special purpose processors. In this paper, we propose an adaptive bulk search (ABS), a framework for solving QUBO that can perform many searches in parallel on multiple GPUs. It supports fully-connected Ising models with up to 32k spins and 16-bit weights. In our ABS, a CPU host performs genetic algorithm (GA) while GPUs asynchronously perform local searches. A bottleneck for solving QUBO exists in the evaluation of the energy function, which requires computational cost for each solution. We show this can be reduced to in our ABS. The experimental results show that, with four NVIDIA GeForce RTX 2080 Ti GPUs, our framework can search up to 1.24 × 1012 solutions per second. We also show that our system quickly solves maximum cut and traveling salesman problems.
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.
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. The graph isomorphism problem is one of the applications of combinatorial optimization, and is not known to be solvable in polynomial time. The problem is also not known to be NP-complete. We propose four QUBO formulations for graph isomorphism problem instances. We also propose four QUBO formulations for induced subgraph isomorphism problem instances and two QUBO formulations for subgraph isomorphism problem instances, which are NP-complete problems. We solve QUBO instances defined by our QUBO formulations, using known QUBO solvers: Gurobi optimizer, Fixstars Amplify AE and OpenJij with SA.
Quadratic unconstrained binary optimization (QUBO) is a classic NP-hard problem with an enormous number of applications. Local search strategy (LSS) is one of the most fundamental algorithmic concepts and has been successfully applied to a wide range of hard combinatorial optimization problems. One LSS that has gained the attention of researchers is the r-flip (also known as r-Opt) strategy. Given a binary solution with n variables, the r-flip strategy “flips” r binary variables to obtain a new solution if the changes improve the objective function. The main purpose of this paper is to develop several results for the implementation of r-flip moves in QUBO, including a necessary and sufficient condition that when a 1-flip search reaches local optimality, the number of candidates for implementation of the r-flip moves can be reduced significantly. The results of the substantial computational experiments are reported to compare an r-flip strategy-embedded algorithm and a multiple start tabu search algorithm on a set of benchmark instances and three very-large-scale QUBO instances. The r-flip strategy implemented within the algorithm makes the algorithm very efficient, leading to very high-quality solutions within a short CPU time.
This paper explores whether reinforcement learning is capable of enhancing metaheuristics for the quadratic unconstrained binary optimization (QUBO), which have recently attracted attention as a solver for a wide range of combinatorial optimization problems. In particular, we introduce a novel approach called the bandit-based variable fixing (BVF). The key idea behind BVF is to regard an execution of an arbitrary metaheuristic with a variable fixed as a play of a slot machine. Thus, BVF explores variables to fix with the maximum expected reward, and executes a metaheuristic at the same time. The bandit-based approach is then extended to fix multiple variables. To accelerate solving multi-armed bandit problem, we implement a parallel algorithm for BVF on a GPU. Our results suggest that our proposed BVF enhances original metaheuristics.
The problem of finding the maximum weighted cycle in a directed graph maps to optimization problems in NP, implying that approaches in classical computing are inefficient. Here, Quantum computing might be a promising alternative. Many current approaches on the quantum computer are based on a Quadratic Unconstrained Binary Optimization (QUBO) problem formulation. This paper develops four different QUBO approaches to this problem. The first two take the starting vertex and the number of vertices used in the cycle as given, while the latter two loosen the second assumption of knowing the size of the cycle. A QUBO formulation is derived for each approach. Further, the number of binary variables required to encode the maximum weighted cycle problem with one or both assumptions for the respective approach is made explicit. The problem is motivated by finding the maximum weighted debt cycle in a debt graph. This paper compares classical computing versus currently avaiable (hybrid) quantum computing approaches for various debt graphs. For the classical part, it investigated the Depth-First-Search (DFS) method and Simulated Annealing. For the (hybrid) quantum approaches, we utilized direct embedding on the quantum annealer and two types of quantum hybrid solvers. Simulated Annealing and the usage of the hybrid CQM (Constrained Quadratic Model) machine functioned promising. The DFS method, direct QPU, and hybrid BQM (Binary Quadratic Model), on the other hand, performed less, due to memory issues, surpassing the limit of decision variables, and finding the right penalty values, respectively.