The Efficient Exact Solution for Binary Quadratic Programming Problems by Quantum Annealing

ORAL

Abstract

Binary quadratic programming problem(BQP) is an optimization problem classified in NP-Hard. Solving BQPs requires time by a conventional solver. It was found that an algorithm combining column generation and quantum annealing or simulated annealing is effective in efficiently obtaining the approximate solution[1]. Column generation is an algorithm that solves linear programming problems efficiently. Quantum annealing is a solver to find the ground state of the Ising model or QUBO. Its properties can be used to solve combinatorial optimization problems. Simulated annealing is also a method for solving combinatorial optimization problems.

The algorithm in [1] derives an approximate solution and is not adapted to real problems. We use branch and bound (BaB) to derive exact solutions[2].

This talk will present an algorithm structure and experimental results that efficiently compute exact solutions using column generation, quantum annealing, and branch-and-bound methods.

* This work is supported by JSPS KAKENHI Grant No. 23H01432.Our study receives financial support from the MEXT-Quantum Leap Flagship Program Grant No. JPMXS0120352009, as well as Publicverb||Private R&D Investment Strategic Expansion PrograM (PRISM) and programs for Bridging the gap between R&D and the IDeal society (society 5.0) and Generating Economic and social value (BRIDGE) from Cabinet Office.

–

Publication: [1] S. Hirama and M. Ohzeki. (2023). Efficient Algorithm for Binary Quadratic Problem by Column Generation and Quantum Annealing, https://arxiv.org/abs/2307.05966
[2] Land, A. H., & Doig, A. G. (1960). An Automatic Method of Solving Discrete Programming Problems. Econometrica, 28(3), 497–520. https://doi.org/10.2307/1910129

Presenters

  • Sota Hirama

    Tohoku University

Authors

  • Sota Hirama

    Tohoku University

  • Masayuki Ohzeki

    Tohoku University, Tokyo Institute of Technology, Sigma-i Co., Ltd