Abstract
Ising machines are expected to solve combinatorial optimization problems efficiently by representing them as Ising models or equivalent quadratic unconstrained binary optimization (QUBO) models . However, upper bound exists on the computable problem size due to the hardware limitations of Ising machines. This paper propose a new hybrid annealing method based on partial QUBO extraction, called subQUBO model extraction, with multiple solution instances. For a given QUBO model, the proposed method obtains $N_I$ quasi-optimal solutions (quasi-ground-state solutions) in some way using a classical computer. The solutions giving these quasi-optimal solutions are called solution instances . We extract a size-limited subQUBO model as follows based on a strong theoretical background: we randomly select $N_S$ $(N_S solution instances among them and focus on a particular binary variable $x_i$ in the $N_S$ solution instances. If $x_i$ value is much varied over $N_S$ solution instances, it is included in the subQUBO model; otherwise, it is not. We find a (quasi-)ground-state solution of the extracted subQUBO model using an Ising machine and add it as a new solution instance. By repeating this process, we can finally obtain a (quasi-)ground-state solution of the original QUBO model. Experimental evaluations confirm that the proposed method can obtain better quasi-ground-state solution than existing methods for large-sized QUBO models.
Funding Information
  • New Energy and Industrial Technology Development Organization (P16007)

This publication has 23 references indexed in Scilit: