シミュレーテッド分岐マシン (SBM) による最大カット問題のベンチマーク

はじめに #

東芝デジタルソリューションズ株式会社が 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 で読むことができます。