Article

2019年9月27日

はじめに

東芝デジタルソリューションズ株式会社が 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$ の値を次のように決めます。

$$ 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: 上記の1ループ終了までの処理を繰り返す数。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} の重み付きグラフの2種類があり、幾何学的な構造としては以下の3種類に分類できます。

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

実行コマンド

簡単のために 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 には先行研究で知られている最良値を入力しています。

instancenodeedgeweighttypetargettime[sec]resultdiff
G180019176+1random116240.02116240
G280019176+1random116200.13116200
G380019176+1random116220.09116220
G480019176+1random116460.02116460
G580019176+1random116310.58116310
G680019176+1,-1random21780.0221780
G780019176+1,-1random20060.0220060
G880019176+1,-1random20050.0220050
G980019176+1,-1random20540.0220540
G1080019176+1,-1random20000.0620000
G118001600+1,-1toroidal5640.015640
G128001600+1,-1toroidal5560.025560
G138001600+1,-1toroidal5820.025820
G148004694+1planar306410.0030631
G158004661+1planar30500.0630500
G168004672+1planar30520.1830520
G178004667+1planar30474.6430470
G188004694+1,-1planar9920.169920
G198004661+1,-1planar9060.029060
G208004672+1,-1planar9410.019410
G218004667+1,-1planar9310.089310
G22200019990+1random133590.20133590
G23200019990+1random133449.99133422
G24200019990+1random133370.07133370
G25200019990+1random133400.45133400
G26200019990+1random133280.07133280
G27200019990+1,-1random33410.0733410
G28200019990+1,-1random32980.2032980
G29200019990+1,-1random34050.0734050
G30200019990+1,-1random34130.2034130
G31200019990+1,-1random33100.7933100
G3220004000+1,-1toroidal14102.0814100
G3320004000+1,-1toroidal13829.7713820
G3420004000+1,-1toroidal13840.7813840
G35200011778+1planar768710.0076807
G36200011766+1planar768010.0176755
G37200011785+1planar769110.0076856
G38200011779+1planar768810.0076862
G39200011778+1,-1planar240810.0024071
G40200011766+1,-1planar24004.9524000
G41200011785+1,-1planar240510.0024041
G42200011779+1,-1planar24819.8724756
G4310009990+1random66600.0266600
G4410009990+1random66500.0266500
G4510009990+1random66540.0266540
G4610009990+1random66490.0266490
G4710009990+1random66570.0266570
G4830006000+1,-1toroidal60000.0760000
G4930006000+1,-1toroidal60000.0760000
G5030006000+1,-1toroidal58800.0758800
G5110005909+1planar38480.9438480
G5210005916+1planar38511.7738510
G5310005914+1planar385010.0038491
G5410005916+1planar385210.0038511
G55500012498+1random1029910.001028910
G56500012498+1,-1random40179.8040089
G57500010000+1,-1toroidal349410.00348014
G58500029570+1planar1929310.011925736
G59500029570+1,-1planar608610.00606719
G60700017148+1random1418810.001416820
G61700017148+1,-1random579610.01577719
G62700014000+1,-1toroidal487010.01484426
G63700041459+1planar2704510.012698659
G64700041459+1,-1planar87518.82872823
G65800016000+1,-1toroidal556210.01553230
G66900018000+1,-1toroidal63649.01632440
G671000020000+1,-1toroidal695010.01690644
G70100009999+1random959110952269
G721000020000+1,-1toroidal700610696640

数千程度の小さな問題については、概ね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/

Tags

About Author

hiroki.kawahara

Leave a Comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

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

Recent Comments

Social Media