最大カット問題#

読み: さいだいかっともんだい
英名: Max Cut Problem

最大カット問題とは，重み付きグラフのノードを２つのグループに分割する問題で，グループ分けをした際にカットされるエッジの重み総和を最大化する．ここで，２つのノードが異なるグループに属したとき，その２点をつなぐエッジがカットされたと言う．

ノードの集合として \(N\) を与え（ノード数は \(n\)），変数として \(x_i \in \{-1,1\}, \ (i \in N)\) を与える．最大カット問題は次のように定式化される．

(49)#\[\begin{split}\begin{array}{ll} \max & \frac{1}{2} \sum_{i,j \in N, i < j}{G_{ij}}(1-x_i x_j) \\ \mathrm{s.t.} & x_i \in \{-1, 1\} \ \ \ \forall i \in N \end{array}\end{split}\]

なお \(G_{ij}\) はノード \(i,j\) 間の重みを表す．上記定式化に対し，変数 \(x_i\) を \(X_{ij}=x_i x_j\) で置き換える変数 \(X_{ij}\) を導入すると，次の問題と同値になる．

(50)#\[\begin{split}\begin{array}{ll} \max & \frac{1}{2} \sum_{i,j \in N, i < j}{G_{ij}}(1-X_{ij}) \\ \mathrm{s.t.} & X \succeq 0 \\ & \mathrm{rank}(X)=1 \\ & X_{ii}=1 \ \ \ \forall i \in N \end{array}\end{split}\]

ここで制約式 \(\mathrm{rank}(X)=1\) を緩和した問題が次の半正定値緩和問題となる．

(51)#\[\begin{split}\begin{array}{ll} \max & \frac{1}{2} \sum_{i,j \in N, i < j}{G_{ij}}(1-X_{ij}) \\ \mathrm{s.t.} & X \succeq 0 \\ & X_{ii}=1 \ \ \ \forall i \in N \end{array}\end{split}\]

上記問題に対して，以下の手順により最大カット問題の実行可能解を生成することができる．

\(v_i \cdot v_j = X_{ij}\) を満たす \(v_i \in \mathbb{R}^n\) を求める．
\(n\) 次元単位球面上の一様分布に従う点 \(r \in \mathbb{R}^n\) を生成する．
\(S=\{ i \in N \mid v_i \cdot r \ge 0 \}\) を，一方のグループとする．

なお，以下のように多次元正規分布を用いて生成することもできる．

\(X\) を分散共分散行列とする多次元正規分布 \(N(0,X)\) に従う \(\xi \in \mathbb{R}^n\) を生成する．
\(S=\{ i \in N \mid \xi_i\ge 0 \}\) を，一方のグループとする．

上記で生成された実行可能解の期待値は元問題の目的関数値の \(\displaystyle\min_{0 \le \theta \le \pi} \displaystyle\frac{2}{\pi} \displaystyle\frac{\theta}{1-\cos \theta} (\ge 0.87856)\) 倍以上になっていることが知られている [1, 2]．