シミュレーテッド分岐マシン (SBM) による最大カット問題のベンチマーク
はじめに
#
東芝デジタルソリューションズ株式会社が AWS Marketplace 上で公開しているシミュレーテッド分岐マシン(Simulated Bifurcation Machinem, 以下 SBM) を試用し、組合せ最適化問題の一つである最大カット問題 (MAX-CUT) を例題にベンチマークしてみました。
SBM
#
SBMは東芝デジタルソリューションズが提供している組合せ最適化ソルバーです。分岐現象・断熱過程・エルゴード過程(カオス)といった古典力学の現象を組合せ最適化に応用し、大規模な問題を高速に解くことができます。
またAWS MarketplaceでPoC版を試すことができます。
最大カット問題
#
SBM で実行できる問題の例として、最大カット問題 (MAX-CUT) を解いてみたいと思います。
最大カット問題とは、与えられた頂点集合において2つの部分集合に分割する際に、異なるグループの間に張られたエッジの重みを最大化する問題です。
目的関数
#
頂点集合
\(V \)
から、
\(S \)
,
\(T \)
の2つの部分集合に分けることを考えます。
頂点
\(v_i \in V \)
が
\(S \)
,
\(T \)
のどちらに含まれるかで、対応する2値変数(Ising変数)
\(s_i \)
の値を次のように決めます。
この続きは Fixstars Tech Blog /proc/cpuinfo で読むことができます。