Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Parallel and Distributed Computing

GPU-accelerated scalable solver with bit permutated cyclic-min algorithm for quadratic unconstrained binary optimization

Ryota Yasudo, Koji Nakano, Yasuaki Ito, Ryota Katsuki, Yusuke Tabata, Takashi Yazane, Kenichiro Hamano

Published Apr 29, 2022• 19 citations
Publisher
DOI
10.1016/j.jpdc.2022.04.016

Related papers

A GPU-Based Quantum-Inspired Parallel Solver for Higher-Order Unconstrained Binary Optimization

Bo-Rong Chen, Jehn‐Ruey Jiang

IEEE International Conference on Consumer Electronics - Taiwan (ICCE-Taiwan)•Jul 1, 2026•0 citations

Graph-theoretic Formulation of QUBO for Scalable Local Search on GPUs

Ryota Yasudo, Koji Nakano, Yasuaki Ito +5 more

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.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 1, 2022•6 citations

A Hybrid Framework Using a QUBO Solver For Permutation-Based Combinatorial Optimization

Siong Thye Goh, Sabrish Gopalakrishnan, Jianyuan Bo +1 more

In this paper, we propose a hybrid framework to solve large-scale permutation-based combinatorial problems effectively using a high-performance quadratic unconstrained binary optimization (QUBO) solver. To do so, transformations are required to change a constrained optimization model to an unconstrained model that involves parameter tuning. We propose techniques to overcome the challenges in using a QUBO solver that typically comes with limited numbers of bits. First, to smooth the energy landscape, we reduce the magnitudes of the input without compromising optimality. We propose a machine learning approach to tune the parameters for good performance effectively. To handle possible infeasibility, we introduce a polynomial-time projection algorithm. Finally, to solve large-scale problems, we introduce a divide-and-conquer approach that calls the QUBO solver repeatedly on small sub-problems. We tested our approach on provably hard Euclidean Traveling Salesman (E-TSP) instances and Flow Shop Problem (FSP). Optimality gap that is less than $10\%$ and $11\%$ are obtained respectively compared to the best-known approach.

arXiv:2009.12767•Sep 27, 2020•4 citations

Unconstrained binary quadratic optimization

Erich Steiner, Th. M. Liebling, Komei Fukuda +1 more

•Jan 1, 2000•1 citation

Diverse Adaptive Bulk Search: a Framework for Solving QUBO Problems on Multiple GPUs

Koji Nakano, Daisuke Takafuji, Yasuaki Ito +5 more

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.

arXiv:2207.03069•IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 1, 2023•20 citations

Heuristic algorithms based on deep reinforcement learning for quadratic unconstrained binary optimization

Ming Chen, Yuning Chen, Yonghao Du +2 more

Knowledge-Based Systems•Aug 8, 2020•18 citations
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.
In this paper, we propose a hybrid framework to solve large-scale permutation-based combinatorial problems effectively using a high-performance quadratic unconstrained binary optimization (QUBO) solver. To do so, transformations are required to change a constrained optimization model to an unconstrained model that involves parameter tuning. We propose techniques to overcome the challenges in using a QUBO solver that typically comes with limited numbers of bits. First, to smooth the energy landscape, we reduce the magnitudes of the input without compromising optimality. We propose a machine learning approach to tune the parameters for good performance effectively. To handle possible infeasibility, we introduce a polynomial-time projection algorithm. Finally, to solve large-scale problems, we introduce a divide-and-conquer approach that calls the QUBO solver repeatedly on small sub-problems. We tested our approach on provably hard Euclidean Traveling Salesman (E-TSP) instances and Flow Shop Problem (FSP). Optimality gap that is less than 10%10\%10% and 11%11\%11% are obtained respectively compared to the best-known approach.
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.