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

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.