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