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.
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.
Recently, extensive studies on photonic reinforcement learning to accelerate the process of calculation by exploiting the physical nature of light have been conducted. Previous studies utilized quantum interference of photons to achieve collective decision-making without choice conflicts when solving the competitive multi-armed bandit problem, a fundamental example in reinforcement learning. However, the bandit problem deals with a static environment where the agent’s actions do not influence the reward probabilities. This study aims to extend the conventional approach to a more general type of parallel reinforcement learning targeting the grid world problem. Unlike the conventional approach, the proposed scheme deals with a dynamic environment where the reward changes because of the agent’s actions. A successful photonic reinforcement learning scheme requires both a photonic system that contributes to the quality of learning and a suitable algorithm. This study proposes a novel learning algorithm, a modified bandit Q-learning method, in view of a potential photonic implementation. Here, state–action pairs in the environment are regarded as slot machines in the context of the bandit problem and a change in Q -value is regarded as the reward of the bandit problem. We perform numerical simulations to validate the effectiveness of the bandit algorithm. In addition, we propose a parallel architecture in which multiple agents are indirectly connected through quantum interference of light and quantum principles ensure the conflict-free property of state–action pair selections among agents. We demonstrate that parallel reinforcement learning can be accelerated owing to conflict avoidance among multiple agents.
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) 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 versatile approach used to represent a wide range of NP-hard Combinatorial Optimization (CO) problems through binary variables. The transformation of QUBO to an Ising Hamiltonian is recognized as an effective method for solving key optimization problems using quantum algorithms. Recently, PI-GNN, a generic framework, has been proposed to address CO problems over graphs based on QUBO with Hamiltonian loss function to train the underlying GNN architecture. Though PI-GNN is highly scalable, it exhibits a noticeable decrease in terms of the number of satisfied constraints with higher graph densities. In this paper, firstly, we identify the limitations and empirically present our strategy to improve PI-GNN’s performance. Secondly, we formulate and evaluate two strategies to integrate QUBO-Hamiltonian as the generic loss function in Reinforcement learning-based (RL) frameworks. The major contribution of our work lies in understanding the feasibility and quality of the QUBO-based generic reward function in an unsupervised RL setup in addressing graph-based CO problems. Empirically, through our empirical evaluation (Our implementation can be found inhttps://tinyurl.com/5apnymz7), we have observed up to 44% improvement in terms of the number of satisfied constraints over PI-GNN in a representative Max-Cut problem.
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) 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.