Efficient Algorithm for Binary Quadratic Problem by Column Generation and Quantum Annealing
arXiv:2307.05966 · doi:10.7566/JPSJ.92.113002
Abstract
We propose an efficient algorithm that combines column generation and quantum annealing to solve binary quadratic problems. Binary quadratic problems are difficult to solve because they are NP-hard. An attempt to solve binary quadratic problems efficiently by column generation has been studied, but it demands successively solving quadratic unconstrained binary optimization problems. We solve the bottleneck by using quantum annealing or simulated annealing. Our results demonstrate a good approximate solution obtained in 2.7 to 1000 times shorter computational time to use column generation and quantum annealing to solve binary quadratic problems than the existing fast solver.
5 pages, 3 figures, 1 Table
References in corpus (6)
- Quantum Annealing for Combinatorial Clustering
- Item Listing Optimization for E-commerce Websites based on Diversity
- Simulated quantum annealing as a simulator of non-equilibrium quantum dynamics
- Fair Sampling by Simulated Annealing on Quantum Annealer
- Virtual Screening of Chemical Space based on Quantum Annealing
- L_1-regularized Boltzmann machine learning using majorizer minimization