東芝シミュレーテッド分岐マシン (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$ の値を次のように決めます。

$$ s_i =
\begin{cases}{}
+1 & (v_i\in S) \\
-1 & (v_i\in T)
\end{cases} $$

この変数を用いて目的関数を以下のように定式化できます。

$$ {\rm max} \ H = \frac{1}{2} \sum_{1\leq i <j \leq n} W_{ij} \left( 1 – s_i s_j \right) $$

頂点 $v_i, v_j$ について、それぞれが異なるグループに属している場合は $\left( 1 – s_i s_j \right) > 0$、同一のグループの場合は $\left( 1 – s_i s_j \right) =0$ となるので、関数 $H$ の最大化により最適な分割がなされます。

多くのアニーリングマシンでは目的関数の最大値ではなく最小値を探索するため、全体に $-1$ を掛けることで最小化問題とすることが出来ます。

$$ {\rm min} \ H = – \frac{1}{2} \sum_{1\leq i <j \leq n} W_{ij} \left( 1 – s_i s_j \right) $$

また、目的関数を Ising変数 $s_i \in \{-1, 1\}$ ではなく、バイナリ変数 $q_i \in \{0, 1\}$ で表す場合、下記の変数変換を用いて書き換えることが出来ます。

$$ q_i = \frac{s_i+1}{2} $$

$$ \begin{aligned}
{\rm min} \ H &= – \frac{1}{2} \sum_{1\leq i <j \leq n} W_{ij} \left(1- (2q_i-1) (2q_j-1) \right) \\
&= \sum_{1\leq i <j \leq n} W_{ij} \left( 2q_iq_j -q_i – q_j \right)
\end{aligned} $$

バイナリ変数 $q_i \in \{0, 1\}$ を受け取るアニーリングマシンの場合、こちらの式を用いて実行します。

SBM の実行

MAX-CUT モード

SBM には 最大カット問題専用のソルバー (MAX-CUTモード) が用意されています。このソルバーは問題を表現するテキストデータを入力することが出来ます。データは MatrixMarket フォーマットか 、最大カット問題のベンチマーク用データセットである Gset フォーマットに対応しています。

Gsetフォーマットは、以下のような空白区切りの整数列で与えられます。

    N E
    i0 j0 w_i0j0
    i1 j1 w_i1j1
    i2 j2 w_i2j2

1行目N、Eはそれぞれ問題グラフの頂点数$N$と辺の数$E$、2行目以降は頂点間$i,j$の辺の重み$w_{ij}$を表しています。

例として、下記に5頂点の最大カット問題を Gset 形式で表しました。

    5 7
    1 2 1
    1 5 1
    2 3 -1
    2 4 1
    2 5 -1
    3 4 -1
    4 5 1

これをグラフ化^[1]すると下記のようになります。

SBMのパラメータ

SBM には下記のポストパラメータを与えることが出来ます。

• steps: SBアルゴリズムの実行ステップ数。これが runs（ソルバー固有の並列数）=320の個数、並列実行されます。この実行ステップ全体を1ループと呼びます。steps を 0 に設定した場合、実行ステップ数が自動設定されます。
• loops: 上記の１ループ終了までの処理を繰り返す数。0に設定した場合、timeout時間まで繰り返します。
• timeout: 実行時間上限秒数。実行時間がこの設定値まで達すると、その時点で実行中のループは破棄され、timeout 到達時点で得られた最良値が解として返されます。
• target(オプション): 終了条件を指定することができます。マシンに与えた目的関数の値がtargetで指定した値に到達すると計算を終了します。
• stats: マシンの出力値の他に以下のような統計的情報を返すかどうか指定することができます。これは runs(並列数) * loops 個の解についての統計です。
  • none: 何も返さない
  • summary: 平均値、標準偏差、最良解の頻度
  • full: 平均値、標準偏差、全解のヒストグラム

先ほどの5頂点の問題を curl コマンドで実行してみました。接続先の 192.168.0.1 は環境に応じて書き換えてください。

 $ echo -e "5 7\n1 2 1\n1 5 1\n2 3 -1\n2 4 1\n2 5 -1\n3 4 -1\n4 5 1" | curl -i -H "Content-Type: application/octet-stream" -X POST "http://192.168.0.1:8000/solver/maxcut?steps=0&loops=0&timeout=1&stats=full" --data-binary @-

今回は下記のパラメータを使用しています。

• steps = 0
• loops = 0
• timeout = 1
• stats = full

正常に実行されると、次のようなレスポンスが得られます。

    HTTP/1.1 200 OK
    Content-Type: application/json; charset=utf-8
    Content-Length: 233
    ETag: W/"e9-6jYjTGcvinFBL6/eKnutYNzItOQ"
    Date: Mon, 19 Aug 2019 03:59:29 GMT
    Connection: keep-alive

    {"id":"r1477108799","time":1,"wait":0,"runs":396800,"steps":10,"message":"timeout","value":3,"result":[0,1,0,0,1],"stats":{"avg":2.441142,"stddev":1.372172,"histogram":[[-2,24009],[-1,4124],[0,15682],[1,12766],[2,12636],[3,327583]]}}

レスポンスの json の代表的なキーは下記のようになっています。

• result: 目的関数を最小化するQUBO変数の組み合わせ
• value: result 変数における目的関数の値
• runs: (実行されたloopsの数)*(ソルバー固有の並列数)

Gsetによるベンチマーク

次に Gset と呼ばれる最大カット問題のベンチマークセットを実行してみます。Gsetのデータセットは以下からダウンロード出来ます。

http://web.stanford.edu/~yyye/yyye/Gset/

Gsetには、G1 – G81 (飛び番あり) の全71個の問題があり、各問題の頂点数は 800 – 20000です。エッジ重み無しグラフと エッジの重み {+1, -1} の重み付きグラフの２種類があり、幾何学的な構造としては以下の３種類に分類できます。

• ランダムグラフ
• 平面グラフ
• トロイダル格子グラフ

実行コマンド

簡単のために curl コマンドにて SBM に Gset をPOSTしてみます。Gset の問題データが配置されたディレクトリに移動し、例えば問題 G1 について、steps=0(自動), loops=0(自動), timeout=10, target=11624 という設定で実行するには、以下のコマンドを入力します。

$ cat G1 | curl -i -H "Content-Type: application/octet-stream" -X POST "http://192.168.0.1:8000/solver/maxcut?steps=0&loops=0&timeout=10&target=11624" --data-binary @-

ベンチマーク結果

以下は G1 – G72 の全69問のデータに対して、steps=0(自動), loops=0(自動), timeout=10, target=(best-known) で実行した結果です。target には先行研究で知られている最良値を入力しています。

数千程度の小さな問題については、概ね1秒以下とかなり高速にターゲットとした最適解の探索に成功していることが分かります。

上記の結果では steps を自動設定としましたが、より性能を引き出すためには steps の調整が有効と思われます。簡単に 60秒の実行時間制約においてどの程度の性能を引き出せるか、G65 を対象に簡単に調査してみました。steps は 10,000～1,000,000 の間で 変化させています。

図中の各点に付記した数字は、そのstepsのもとで実行時間60秒とした時のループ回数です。

G65では500,000以上のような大きなstepsを設定するほうが、小さなstepsのループを 多く実行するよりも効率がいいという傾向がみられました。

このように、問題によって短いループを多数回まわす方が良いか、あるいはある程度長い1ループを実行するほうが良いのか異なる場合があるため、効率よく解を得るためには最適なsteps設定を見つけることが鍵になるのかもしれません。

まとめ

SBM は最大カット問題に対し高速に近似解を得られることが体験できました。特に頂点数$N=2000$ 程度の比較的小さい問題では概ね1秒以下で最適解に到達していました。

最大カット問題は、イジング定式化された組合せ最適化問題のなかでは、制約項のない比較的解きやすい問題だと考えられています。今回はベンチマークとして最大カット問題と Gset を例に取り上げましたが、より複雑かつ実用的な組合せ最適化問題についても期待が持てるのではと思われます。また、チューニング次第でどこまで高速あるいは高精度な解が出せるのか、継続して調査していく予定です。

1. https://csacademy.com/app/graph_editor/

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。