Mercari Engineering Blog

We're the software engineers behind Mercari. Check out our blog to see the tech that powers our marketplace.

D-waveマシンで最大カット問題を解く

こんにちは。Professional Internshipでインターンをしていた、@ukunです(9/7をもってインターン終了)。この記事では、インターン期間中に取り組んだ内容(最大カット問題に対するD-Waveマシンの性能評価)について紹介します。前半はD-Waveや扱った問題について、後半は具体的な実験内容とその結果について説明しています。

D-Waveマシンとは

カナダのD-Wave Systemsというベンチャー企業によって開発された、量子アニーリングというメタヒューリスティクスを実行する専用機です。

D-Waveで扱える問題

D-Waveは、以下のようなIsing modelのハミルトニアンの基底状態を求める問題や、

$$
\mathrm{min.\quad} \sum_{1 \le i< j \le n} J_{ij} \sigma_i \sigma_j + \sum_{1 \le i \le n} h_i \sigma_i \\
\mathrm{s.t.\quad} \sigma_i \in \{-1, 1\} ,\quad \forall i \in \{1, \dots, n\}
$$

以下のような Quadratic Unconstrained Binary Optimization (QUBO)という問題

$$
\mathrm{min. \quad} x^\top Qx \\
\mathrm{s.t. \quad} x \in \{0, 1\}^n
$$

の精度保証がない近似解を求めることができます。また, Ising modelとQUBOの問題は等価に変換することができます。ここで、最小化もしくは最大化したい関数を目的関数といいます。

テーマの背景

ここまで、以下の2点について簡単に導入しました。

  • D-Waveは量子アニーリングという手法を実装している
  • D-WaveはIsing modelやQUBOの形で書ける問題の近似解を得ることができる

では、得られる近似解やそれに対応する目的関数の値はどれほど最適値に近いのでしょうか??

量子アニーリングは、解の最適性や精度について理論的な保証がありません。そこで、量子アニーリングで得られた解の精度について経験的な知見を得たいというのが今回のテーマの目的です。しかし、最初から一般の問題について考えるのは大変なので、今回は最大カット問題について考えることにしました。

最大重みカット問題

最大重みカット問題とは、入力として無向グラフ \(G = (V, E)\) と辺重み\(w \colon E \to \mathbb R\)が与えられたとき、出力として
$$
\newcommand{\argmax}{\mathop{\rm arg~max}\limits}
\argmax_{S \subseteq V} {\sum_{v\in S, u\in V \backslash S} w(\{u, v\})}
$$
を求める問題です。これは、グラフの頂点からある頂点の集合\(S\)を取り除いて、\(V\)に残った頂点と\(S\)に含まれる頂点の間の辺の重みの和を最大化する問題です。また、この分割をカット、カットをまたぐ辺の重みの和をカットサイズといいます。

以下に最大カット問題の例を示します。下図のように、頂点 \(V = \{1, 2, 3, 4\}\) と辺 \(E = \{\{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\}\}\)のグラフ\(G = (V, E)\)が与えられたとします。また、簡単のために辺重みはすべて1とします。このとき、最大カット問題の解の一つは、黒く色付けされた頂点の集合\(S = \{1, 2\}\)となり、またそのカットサイズは赤く色付けされた辺の本数である4となります。

f:id:hal0taso:20180906184608j:plain:w500

この問題はNP-hardという計算量クラスに属しています*1。また、辺重みがすべて1の最大カット問題の判定問題*2NP-completeという計算量クラスに属しており、次数が高々3でもNP-completeです*3

\(V = \{1, \dots ,n\}\) とし、\(1 \le i, j \le n\) に対して \(\{i, j\} \in E\) なら \(w_{ij} = w(\{i, j\})\)、そうでないなら \(w_{ij} = 0\) とします。また、変数 \(x_i = 1\)のとき、そしてそのときのみ\(i \in S\)として、\(x_i \in \{-1, 1\}\)とします。すると、最大重みカット問題は、以下のように定式化することができます。

$$
\mathrm{max.\quad} \frac{1}{2} \sum_{1 \le i< j \le n} w_{ij} (1 - x_i x_j) \\
\mathrm{s.t.\quad} x_i \in \{-1, 1\} ,\quad \forall i \in \{1, \dots, n\}
$$

この問題が先ほどの Ising model の式と同じ形をしていることを見ていきましょう。上の問題は、定数項を無視し、最大化問題の目的関数を\(-1\)倍して以下のような最小化問題として考えることができます。\(h\)の係数が全て0の場合と等価なことがわかるので、ナイーブな定式化でD-Waveで扱える問題になっていることがわかります。

$$
\mathrm{min.\quad} \frac{1}{2} \sum_{1 \le i< j \le n} w_{ij} x_i x_j \\
\mathrm{s.t.\quad} x_i \in \{-1, 1\} ,\quad \forall i \in \{1, \dots, n\}
$$


実験した内容

今回は、3-正則グラフについて、以下の3つの場合について調べました。

  • 辺重みが全て\(1\)
  • 辺重みを\((0, 10]\)でランダムに選ぶ
  • 辺重みを\((-10, 10]\)でランダムに選ぶ

D-Waveは、ハードウェアの仕様上、Ising modelやQUBOの形に定式化した問題をキメラグラフという特殊なグラフ上で表現する必要があります。元の問題をキメラグラフ上で表現するために、埋め込みという操作が必要な場合があります*4

3-正則グラフは、200頂点まで埋め込むことができることが知られています*5。実際、私が実験を行った際にも、200頂点までの3-正則グラフを埋め込むことができました*6

また、

今回は、以下の設定で実験を行いました。

  • 使用するのはD-Wave 2000Q
  • 頂点数は50から200まで10ずつ変化させる
  • 辺重みは前述の3通りの設定を試す
  • アニーリング回数を100、1000でそれぞれ変化させる
  • accuracyを$$\mathrm{accuracy} = (Obj_{dw} - lb)/(Obj_{gurobi} - lb)$$とし、それをグラフにプロットし、頂点数によってそのaccuracyがどう変化するかを調べる。ただし、\( (Obj_{dw} \)をD-Waveによって得られた解の目的関数値、\( (Obj_{gurobi} \)を最適化ソルバーGurobiによって得られた解の目的関数値、\(lb\) を目的関数値の下界とする。

ここでアニーリング回数とは、D-Waveで問題を解かせる回数をといいます。D-Waveで問題を解かせる際には、同じ問題に対して何度も別々にアニーリングを実行し、そのうちの最良の結果を今回の出力とします。


実験結果

アニーリング回数が1000回で実験を行った結果、以下の図のようになりました。


f:id:hal0taso:20180907200511p:plain:w500

ここで、赤色のグラフは重みが全て1、青色のグラフは重みを\( (-10, 10] \)でランダムに選んだもの、緑色のグラフは重みを\( (0, 10] \)でランダムに選んだものになります。点は各インスタンスで得られた近似率、折れ線はその平均値を示しています。また、100回アニーリングした結果は以下の図のようになりました。

f:id:hal0taso:20180907200547p:plain

重みなしよりも、重みのあるインスタンスのほうが頂点数に対してaccuracyの減少の速さが大きくなっていることがわかります。正重みと一般の重みでは、accuracyはほとんど一緒でした。また、100回アニーリングするよりも1000回アニーリングした方が平均の近似率は高そうです。何度も解かせたうち最良の結果を出力としているので、自然な結果だと思います。実際に、重みが全て1の場合に、アニーリング回数で比較すると以下の図のようになります。それぞれ、赤は1000回、青は100回、緑は10回、ピンクは1回のアニーリング回数です。他の重みの付け方についても同様でした。


f:id:hal0taso:20180907200713p:plain

まとめ

今回のインターンでは、D-Waveマシンを使って最大カット問題を解いたときの、その精度がどのように変化するのか調べました。その結果、重みがある方が解の精度が減少する速度が早くなることがわかりました。
今回取り扱った問題は、制約なしかつナイーブな定式化でIsing modelと等価な問題に変形できる問題なのでD-Waveと相性がよかったですが、制約ありの問題に対してはD-Waveでどのようにアプローチするのがよいのか考えてみる余地があると思いました*7

現状のD-Waveは、解ける問題のサイズがまだとても小さかったり*8、制約ありの問題をあつかう際には、最適解が得られるとは限らないため得られる解が制約を満たしている保証がなかったりと課題が多くあります。また、量子アニーリングの分野としても、理論的に明らかにされていない問題が多くあったり、まだまだ未開拓の分野でやることがたくさんある分野だと感じました。

*1:M. R. Garey, D. S. Johnson, L. Stockmeyer, "Some simplified NP-complete problems", Proceeding of STOC, pp47-63, 1974

*2:最大カット問題の判定問題は、グラフ\(G\) と整数\(K \in \mathbb N\)が入力として与えられたとき、カットサイズが\(K\)以上となるカットが存在するならYes, 存在しないならNoを出力として求める問題です

*3:M. R. Garey, D. S. Johnson, "Computers and Intractability -A Guide to the Theory of NP-Completeness", W. H. Freeman, 1979

*4:グラフマッピング – 量子コンピュータ情報サイト

*5:J. Cai, W. G. Macready, A. Roy, "A practical heuristic for finding graph minors", arXiv preprint arXiv:1406.2741 2014

*6:190頂点、200頂点の場合には、D-Waveが提供しているツールでは埋め込めないグラフもあるようでした

*7:Quadratic Assignment Problemを解いてみるとおもしろいのではないか、と聞きました

*8:キメラグラフ上に埋め込む完全グラフは、64頂点までしか埋め込めません