2019-09-27

シミュレーテッド分岐マシン (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 で読むことができます。