抄録
We propose a spin-variable reduction method for Ising machines to handle linear equality constraints in a combinatorial optimization problem. Ising machines including quantum-annealing machines can effectively solve combinatorial optimization problems. They are designed to find the lowest-energy solution of a quadratic unconstrained binary optimization (QUBO), which is mapped from the combinatorial optimization problem. The proposed method reduces the number of binary variables to formulate the QUBO compared to the conventional penalty method. We demonstrate a sufficient condition to obtain the optimum of the combinatorial optimization problem in the spin-variable reduction method and its general applicability. We apply it to typical combinatorial optimization problems, such as the graph kk-partitioning problem and the quadratic assignment problem. Experiments using simulated-annealing and quantum-annealing based Ising machines demonstrate that the spin-variable reduction method outperforms the penalty method. The proposed method extends the application of Ising machines to larger-size combinatorial optimization problems with linear equality constraints.
本文言語 | English |
---|---|
ページ(範囲) | 2151-2164 |
ページ数 | 14 |
ジャーナル | IEEE Transactions on Computers |
巻 | 72 |
号 | 8 |
DOI | |
出版ステータス | Published - 2023 8月 1 |
ASJC Scopus subject areas
- ソフトウェア
- 理論的コンピュータサイエンス
- ハードウェアとアーキテクチャ
- 計算理論と計算数学