Spin-Variable Reduction Method for Handling Linear Equality Constraints in Ising Machines

Tatsuhiko Shirai*, Nozomu Togawa

*この研究の対応する著者

研究成果: Article査読

3 被引用数 (Scopus)

抄録

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

  • ソフトウェア
  • 理論的コンピュータサイエンス
  • ハードウェアとアーキテクチャ
  • 計算理論と計算数学

フィンガープリント

「Spin-Variable Reduction Method for Handling Linear Equality Constraints in Ising Machines」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル