この記事はJij Advent Calendar 2024の6日目の記事です.
QAOAやQuantum Annealingでは,イジングモデルでかけるという理由で,例題でよくMaxcut問題を扱うことが多い.その時に,性能のベースラインとしてよく使われるのが,Goemans-Williamson Algorithmである.このアルゴリズムはそれ自体が非常に面白いので,この記事はGoemans-Williamson Algorithmについて自分が勉強したまとめである.
Maxcut問題
Maxcut問題は,無向グラフ G(V,E)とエッジの重み w:E→R+が与えられたとき,ノードを U⊂Vと W⊂Vに分け,両端が Uに属するノードと Wに属するノードになっているエッジの合計を最大化する問題である.
例えば,以下の左の図のようなグラフが与えられたとする.
右の図のようにノードを塗り分ける(組を作る)ことで,ほとんどの隣り合うノードが別の組に入る分け方が実現できることがわかる.

Maxcut問題は,以下のように定式化することができる.
ノード viが Uに属するとき si=1, Wに属するとき, si=−1となる変数 si∈{1,−1}を定義する.
このとき,エッジの両端 (i,j)∈Eが同じ集合に含まれているとき, sisj=1であり,異なる集合に含まれているとき sisj=−1である.
この性質を用いると,次の数理モデルを作ることができる.
max21(i,j)∈E∑wij(1−sisj)(1)
ここで係数の1/2は,異なる組に入っているときに1−sisj=2となるので,それを補正するためにかけている.
Goemans-Williamson Algorithm
Goemans-Williamson Algorithm(GW)は,Maxcut問題に対する近似アルゴリズムの一つである[1].このアルゴリズムについては,[2-4]に良い説明があるので,そちらを読む方が有意義かなとは思う.ここでは,[2-4]をベースにして,このアルゴリズムを説明しようと思う.
GWは,
- 問題(1)に対する適当な緩和問題を作る
- 緩和問題の解をうまく丸めて元の問題の解になるようにする
という二つのステップで構成されている.
緩和問題の作成
まずは,問題(1)をベクトル計画問題に緩和した問題を考える.
ベクトル計画問題は,変数がベクトル vi∈Rnで表現され,目的関数と制約条件がベクトルの内積 vi⋅vjに対して線形で表現される問題である.
問題(1)をベクトル計画問題に緩和した問題は,次のように記述することができる.
maxs.t.21(i,j)∈E∑wij(1−vi⋅vj)vi⋅vi=1 ∀ivi∈Rn ∀i(2)
問題(1)のどんな実行可能解 yiもvi=(yi,0,…,0)とすれば, vivi=1と vivj=yiyjを満たし,ベクトル計画問題(2)の実行可能解になるので,ベクトル計画問題は元の問題の緩和問題になっていることがわかる.
また,この問題は vi⋅vi=1という制約条件から, viは Rn空間上の単位円 Sn上に解は分布することもわかる.
次に,上記のベクトル計画問題をさらに半正定値計画問題に変換する.
上記のベクトル計画問題では,変数は内積vi⋅vjの形でしか表れていないので,内積 vi⋅vjを半正定値計画の変数 yijに変換する.これによって,目的関数と制約条件は yijに対して線形となる.さらに, yijを要素にもつ行列 Y∈Rn×nは,簡単な計算からYは半正定値行列であることがわかる.
以上から,ベクトル計画問題(2)を半正定値計画問題へと変換した結果得られる問題は,
maxs.t.21(i,j)∈E∑wij(1−yij)yii=1 ∀iY⪰0Y∈Mn(3)
とかける.ここで, Mnは実 n×n行列の対称錐の集合であり,vi⋅vi=1の制約条件から,yii=1という制約条件をかけている.
この半正定値計画は内点法などを用いることで多項式時間で解くことができる.
実際に,上記の半正定値計画問題をソルバーで解きやすくするために標準形に持っていく.
これにはグラフラプラシアンLを用いるのが便利である.
グラフラプラシアンLは,隣接行列Aと次数行列Dを用いて,L=D−Aと書くことができ,このグラフラプラシアンを用いて,式(3)は
maxs.t.21L∙Yyii=1 ∀iY⪰0Y∈Mn(4)
と書き直すことができる.
ここでは,上で挙げた簡単な例を解いてみることにする.
グラフラプラシアンは
で得ることができる.
さて,これをソルバーで解いてみよう.
ここでは,cvxpy
で実装して,それに付随しているソルバーで解くことにする.
で解くことができる.
ラウンディングアルゴリズム
問題(3)の半正定値計画の解は得られたとして,次にこの解をどのように元の問題の解に戻すのかを考えよう.
得られた解 Yを特異値分解などを使えば,Y=VTVとなるような Vを得ることができるので,ベクトル計画問題(2)の解を得ることができる.
さて,ベクトル計画問題(2)の最適解 u1,…,unを得た.ここからどのように,(1)の解を得るかを考える.
二つのベクトル ui,ujのなす角度を θijとすると, ∣u∣=1なので, ui⋅uj=cosθij.
よって,ベクトル計画問題の目的関数は,
21(i,j)∈E∑wij(1−cosθij)
となる.この目的関数を最大化するには, θijが πに近い方がよい.つまり, θijが大きいときに ui,ujを別の組になるようにすればいい.
そこで,以下の方法で,indexの集合を分類することにする.
初めにn次元球面上から一様ランダムにベクトル rをサンプルする.このベクトルは各成分を正規分布 N(0,1)からサンプルし,規格化することで得ることができる.
このrを用いて, vi⋅r≥0となるベクトルのindexを Uに入れ,それ以外を Wに入れることで,全てのノードindexを Uと Wに分類することができる.
この方法についてもう少し詳しく述べよう.uiと ujが分離されるのは,ベクトル rに対して,
-
ui⋅r≥0かつ uj⋅r≤0
-
ui⋅r≤0かつ uj⋅r≥0
のどちらかの場合である.
uiとujが張る2次元平面を考え, rをこの平面に射影することを考える.rは球面対称な分布にしたがっているので,この2次元射影した円に対しても一様に分布する.
ここで, ui⋅r≥0かつ uj⋅r≤0もしくは, ui⋅r≤0かつ uj⋅r≥0となるのは,rがuiと ujが作る弧の間つまり, θijの範囲にくる場合である.よって,その範囲に rがくる確率は 2θij/2π=θij/πである.
つまり,θijがπに近いほど分離される確率が高くなることがわかる.
実際に,この方法で,(1)の解を得てみよう.
ちなみに,実際に得られた結果をプロットしたのが,冒頭に載せた右の図である.
近似率について
さて,最後に近似率について簡単に議論しておこう.
まず初めに,カットされた重みの期待値 E[W]を計算してみる.uiと ujが分離される確率がθij/πであることを思い出すと,
E[W]=(i,j)∈E∑wijπθij
である.
ここで,天下り的だが,αが
α=π20≤θ≤πmin1−cosθθ≈0.87856…
で与えられるとしよう.
この定義からα≤π21−cosθθなので,
πθ≥2α(1−cosθ)
が成り立つ.これを代入すると,
E[W]≥α(i,j)∈E∑wij2(1−cosθij)
となる.右辺はベクトル計画問題(2)の最適値 OPTvであり,問題(2)は問題(1)の緩和問題であることを使うと,OPTv≥OPTなので,
E[W]≥αOPT
が成り立つ.これはアルゴリズムの解の精度と最適値の比に対して,
よって,GWの近似率はα≈0.878である.
最後に
Jijでは数理最適化・量子コンピュータに関連するソフトウェア開発を行っています。
OSSも複数開発、提供しています。Discordのコミュニティへぜひ参加してください!
https://discord.gg/Km5dKF9JjG
また,Jijでは各ポジションを絶賛採用中です!
ご興味ございましたらカジュアル面談からでもぜひ!ご連絡お待ちしております。
数理最適化エンジニア(採用情報)
量子コンピューティングソフトウェアエンジニア(採用情報)
Rustエンジニア(アルゴリズムエンジニア)(採用情報)
研究チームPMO(採用情報)
オープンポジション等その他の採用情報はこちら
参考文献
[1]Michel X Goemans and David P Williamson. “Improved approximation algorithms for maximum
cut and satisfiability problems using semidefinite programming”. In: Journal of the ACM (JACM)
42.6 (1995)
[2]Vijay V Vazirani. Approximation algorithms. Vol. 1. Springer, 2001.
[3]David P Williamson and David B Shmoys. The design of approximation algorithms. Cambridge
university press, 2011.
[4]Matsui Tomomi. “OR 研究の最前線 半正定値計画を用いた最大カット問題の.878 近似解法”. In:
オペレーションズ・リサーチ = Communications of the Operations Research Society of Japan: 経
営の科学 45.3 (Mar. 2000)
Discussion