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.
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.
The main contribution of this paper is to present a simple exhaustive search algorithm for the quadratic unconstraint binary optimization (QUBO) problem. It computes the values of the objective function E(X) for all n-bit input vector X in O(2n) time. Since Ω(2n) time is necessary to output E(X) for all 2nvectors X, this sequential algorithm is optimal. We also present a work-time optimal parallel algorithm running O(log n) time using 2n/ log n processors on the CREW-PRAM. This parallel algorithm is work optimal, because the total number of computational operations is equal to the running time of the optimal sequential algorithm. Also, it is time optimal because any parallel algorithm using any large number of processors takes at least Ω(log n) time for evaluating E(X). Further, we have implemented this parallel algorithm to run on the GPU. The experimental results on NVIDIA GeForce RTX 2080Ti GPU show that our GPU implementation runs more than 1000 times faster than the sequential algorithm running on Intel Corei7-8700K CPU(3.70GHz) for the QUBO with nbit vector whenever n ≥ 33. We also compare our exhaustive search parallel algorithm with several non-exhaustive search approaches for solving the QUBO including D-Wave 2000Q quantum annealer, simulated annealing algorithm, and Gurobi optimizer.
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.
Quadratic Unconstrained Binary Optimization (QUBO) has emerged as a unifying framework for diverse NP-hard combinatorial optimization problems. However, a major challenge in existing QUBO solvers is the need for extensive manual tuning of algorithmic hyperparameters, such as temperature schedules in simulated annealing, which can vary greatly in effectiveness depending on the problem instance. In this paper, we propose RL-assisted annealing(RLA), a novel approach that integrates reinforcement learning (RL) with annealing-based local searches. Rather than relying on hand-crafted heuristics, RLA trains an agent to adaptively determine a bit-flip policy by observing the statistical properties of the energy differences in the objective function. Crucially, RLA encodes QUBO states as fixed-dimensional statistics, making the method scalable to various problem sizes. To further support large-scale problems, we employ distributed training on multi-GPU platforms using JAX’s pmap, parallelizing both environment simulation and policy updates. Experimental evaluations on benchmark datasets, including TSP, QAP, Max-Cut, and randomly generated QUBO instances, demonstrate that RLA achieves solution qualities on par with or better than conventional annealing-based methods, while maintaining robust performance across diverse problem instances without extensive hyperparameter tuning. These results highlight RLA as a promising step toward a flexible and practical solver for QUBO-based applications.
Quadratic Unconstrained Binary Optimization (QUBO) has emerged as a unifying framework for diverse NP-hard combinatorial optimization problems.However, a major challenge in existing QUBO solvers is the need for extensive manual tuning of algorithmic hyperparameters, such as temperature schedules in simulated annealing, which can vary greatly in effectiveness depending on the problem instance.In this paper, we propose RL-driven annealing (RLA), a novel approach that integrates reinforcement learning (RL) with annealing-based local searches.Rather than relying on hand-crafted heuristics, RLA trains an agent to adaptively determine a bit-flip policy by observing the statistical properties of the energy differences in the objective function.Crucially, RLA encodes QUBO states as fixed-dimensional statistics, making the method scalable to various problem sizes.To further support large-scale problems, we employ distributed training on multi-GPU platforms using JAX's pmap, parallelizing both environment simulation and policy updates.Experimental evaluations on benchmark datasets, including TSP, QAP, Max-Cut, and randomly generated QUBO instances, demonstrate that RLA achieves solution qualities on par with or better than conventional annealing-based methods, while maintaining robust performance across diverse problem instances without extensive hyperparameter tuning.These results highlight RLA as a promising step toward a flexible and practical solver for QUBO-based applications.
This paper proposes a novel framework for automatically setting penalty weights in the Quadratic Unconstrained Binary Optimization (QUBO) to handle problems with multiple constraints. Quantum computing and quantum-inspired methods have gained prominence, with QUBO models widely used for their unified representation of optimization problems. However, QUBO performance is highly sensitive to penalty weight settings, especially in multiple constraints scenarios, where setting different penalty weights to different constraints may further affect performance. Existing methods for setting common penalty weights for all constraints in QUBO can be generally categorized into manual methods based on expert experience, exact methods based on the objective function values, and sequential methods based on searching within an upper bound. This study introduces a novel framework for multiple constraints optimization that utilizes exact and sequential binary search methods to determine common penalty weight while integrating constraint sensitivity analysis to adjust each penalty weight dynamically. This approach enhances the efficiency and quality of QUBO solutions. Experimental results on the Travelling Salesman Problem show that the proposed framework achieves superior solution quality and feasibility on both the D-Wave quantum annealer and classical simulated annealing solvers, outperforming traditional methods and demonstrating strong adaptability.