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

arXiv:1706.00037

A Diversified Multi-Start Algorithm for Unconstrained Binary Quadratic Problems Leveraging the Graphics Processor Unit

Mark W. Lewis

Published May 31, 2017• 0 citations
arXivHTMLPDF

Abstract

Multi-start algorithms are a common and effective tool for metaheuristic searches. In this paper we amplify multi-start capabilities by employing the parallel processing power of the graphics processer unit (GPU) to quickly generate a diverse starting set of solutions for the Unconstrained Binary Quadratic Optimization Problem which are evaluated and used to implement screening methods to select solutions for further optimization. This method is implemented as an initial high quality solution generation phase prior to a secondary steepest ascent search and a comparison of results to best known approaches on benchmark unconstrained binary quadratic problems demonstrates that GPU-enabled diversified multi-start with screening quickly yields very good results.

DOI
10.48550/arxiv.1706.00037

Related papers

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

Quadratic Unconstrained Binary Optimization via Quantum-Inspired Annealing

Joseph Bowles, Alexandre Dauphin, Patrick Huembeli +2 more

We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimization. The algorithm can be seen as an analog of quantum annealing under the restriction of a product-state space, where the dynamical evolution in quantum annealing is replaced with a gradient-descent-based method. This formulation is able to quickly find high-quality solutions to large-scale problem instances and can naturally be accelerated by dedicated hardware such as graphics processing units. We benchmark our approach for large-scale problem instances with tunable hardness and planted solutions. We find that our algorithm offers a similar performance to current state-of-the-art approaches within a comparably simple gradient-based and nonstochastic setting.

Physical Review Applied•Sep 7, 2022•23 citations

Adaptive Bulk Search: Solving Quadratic Unconstrained Binary Optimization Problems on Multiple GPUs

Ryota Yasudo, Koji Nakano, Yasuaki Ito +4 more

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.

Proceedings of the International Conference on Parallel Processing•Aug 9, 2020•12 citations

Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing

Joseph Bowles, Alexandre Dauphin, Patrick Huembeli +2 more

We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. The algorithm can be seen as an analogue of quantum annealing under the restriction of a product state space, where the dynamical evolution in quantum annealing is replaced with a gradient-descent based method. This formulation is able to quickly find high-quality solutions to large-scale problem instances, and can naturally be accelerated by dedicated hardware such as graphics processing units. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions. We find that our algorithm offers a similar performance to current state of the art approaches within a comparably simple gradient-based and non-stochastic setting.

arXiv:2108.08064•Aug 18, 2021•0 citations

GPU-based Ising Machine for Solving Combinatorial Optimization Problems with Enhanced Parallel Tempering Techniques

Kuei-Po Huang, Chin-Fu Nien, Yun-Ting Zhang +2 more

Ising machines (IMs) are hardware solvers designed to tackle computationally complex combinatorial optimization problems (COPs), harnessing physical processes such as quantum annealing to simulate the Ising model, enabling these specially designed solvers to tackle a wide range of computationally complex NP-hard problems in real-world applications, such as portfolio optimization and logistics planning. While prior works propose to fabricate dedicated integrated circuits for building IMs, we leverage off-the-shelf Graphics Processing Unit (GPU) chips for implementing Ising algorithms for quick development. In this work, we explore parallel tempering (PT), an Ising algorithm, which shows promise owing to its capability for parallel processing of multiple independent searches for the optimal solution, each with a different amount of randomness that allows escaping local minima. We propose several optimization strategies, including addressing the dependency problem in PT to enhance algorithm parallelism and integrating genetic algorithm (GA)-like operations to increase the diversity of the search process for effective solution discovery. Empirical evaluations demonstrate that our proposed Parallel Quantum-inspired Search (PQS) solver achieves a $2.66 \times$ speedup over the state-of-the-art GPU-based solution without sacrificing solution quality.

IEEE Asia Pacific Conference on Circuits and Systems (APCCAS)•Nov 7, 2024•3 citations

Digital Annealing Engine for High-speed Solving of Constrained Binary Quadratic Problems on Multiple GPUs

Kentaro Katayama, Noboru Yoneoka, Kouichi Kanda +3 more

This paper presents a digital annealing engine capable of high-speed solving the Binary Quadratic Programming Problem (BQP) with equality and inequality constraints. While many Quadratic Unconstrained Binary Optimization (QUBO) solvers have been developed for combinatorial optimization problems, they are specialized for “unconstrained” BQP and struggle to solve “constrained” BQP at high speed. To address this issue, we developed a digital annealing engine on GPUs that leverages constraints to narrow the search space and directly evaluates inequality violations during Markov Chain Monte Carlo based searches. We evaluated the performance of the Digital Annealer (DA) system with the developed engine on benchmark problems with one-hot (a type of equality constraint) and inequality constraints. The results showed that the developed DA system achieved superior solving performance compared to the previous generation of DA. It also showed comparable performance to state-of-the-art dedicated solvers. Our results suggest that this digital annealing engine is a promising solution for high-speed solving constrained BQP.

International Conference on Consumer Electronics•Jan 6, 2024•5 citations
Multi-start algorithms are a common and effective tool for metaheuristic searches. In this paper we amplify multi-start capabilities by employing the parallel processing power of the graphics processer unit (GPU) to quickly generate a diverse starting set of solutions for the Unconstrained Binary Quadratic Optimization Problem which are evaluated and used to implement screening methods to select solutions for further optimization. This method is implemented as an initial high quality solution generation phase prior to a secondary steepest ascent search and a comparison of results to best known approaches on benchmark unconstrained binary quadratic problems demonstrates that GPU-enabled diversified multi-start with screening quickly yields very good results.
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.
We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimization. The algorithm can be seen as an analog of quantum annealing under the restriction of a product-state space, where the dynamical evolution in quantum annealing is replaced with a gradient-descent-based method. This formulation is able to quickly find high-quality solutions to large-scale problem instances and can naturally be accelerated by dedicated hardware such as graphics processing units. We benchmark our approach for large-scale problem instances with tunable hardness and planted solutions. We find that our algorithm offers a similar performance to current state-of-the-art approaches within a comparably simple gradient-based and nonstochastic setting.
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.
We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. The algorithm can be seen as an analogue of quantum annealing under the restriction of a product state space, where the dynamical evolution in quantum annealing is replaced with a gradient-descent based method. This formulation is able to quickly find high-quality solutions to large-scale problem instances, and can naturally be accelerated by dedicated hardware such as graphics processing units. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions. We find that our algorithm offers a similar performance to current state of the art approaches within a comparably simple gradient-based and non-stochastic setting.
Ising machines (IMs) are hardware solvers designed to tackle computationally complex combinatorial optimization problems (COPs), harnessing physical processes such as quantum annealing to simulate the Ising model, enabling these specially designed solvers to tackle a wide range of computationally complex NP-hard problems in real-world applications, such as portfolio optimization and logistics planning. While prior works propose to fabricate dedicated integrated circuits for building IMs, we leverage off-the-shelf Graphics Processing Unit (GPU) chips for implementing Ising algorithms for quick development. In this work, we explore parallel tempering (PT), an Ising algorithm, which shows promise owing to its capability for parallel processing of multiple independent searches for the optimal solution, each with a different amount of randomness that allows escaping local minima. We propose several optimization strategies, including addressing the dependency problem in PT to enhance algorithm parallelism and integrating genetic algorithm (GA)-like operations to increase the diversity of the search process for effective solution discovery. Empirical evaluations demonstrate that our proposed Parallel Quantum-inspired Search (PQS) solver achieves a 2.66×2.66 \times2.66× speedup over the state-of-the-art GPU-based solution without sacrificing solution quality.
This paper presents a digital annealing engine capable of high-speed solving the Binary Quadratic Programming Problem (BQP) with equality and inequality constraints. While many Quadratic Unconstrained Binary Optimization (QUBO) solvers have been developed for combinatorial optimization problems, they are specialized for “unconstrained” BQP and struggle to solve “constrained” BQP at high speed. To address this issue, we developed a digital annealing engine on GPUs that leverages constraints to narrow the search space and directly evaluates inequality violations during Markov Chain Monte Carlo based searches. We evaluated the performance of the Digital Annealer (DA) system with the developed engine on benchmark problems with one-hot (a type of equality constraint) and inequality constraints. The results showed that the developed DA system achieved superior solving performance compared to the previous generation of DA. It also showed comparable performance to state-of-the-art dedicated solvers. Our results suggest that this digital annealing engine is a promising solution for high-speed solving constrained BQP.