最適化セミナーのご案内

2.23 隣接行列(最大カット問題)

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

 この問題は,グラフ構造が隣接行列で与えられるという特徴を持ちます.また,数理計画法としては,SDP緩和問題として良質な上界値を求めることができる例題として知られています.

例題

 次のグラフは,ノードとして1,2,3,4,5,6を持つ重み付きグラフです.エッジがない場合は,重みを0とします.

 ノードを二つのグループに分けて,カットされるエッジの重みの総和を最大化したい場合,どのようなグループとなるでしょうか.

 この問題をNumerical Optimizerで解くために定式化を行いますが,まずはSDP緩和問題として定式化し,目的関数値の上界値を求めてみましょう.V13からVector/Matrixクラスが利用できるようになったため,ラプラス行列の計算を簡単に表現することができるようになりました.ここでラプラス行列とは,グラフの次数行列と隣接行列が与えられたとき,次数行列から隣接行列を引いた行列で定義されます.

 以下で紹介する定式化は参考文献[7]によります.まず,ノードの集合として$N$を与え,変数として$x_i \in \{-1,1\}, (i \in N)$を与えます.このとき,ノード$i,j \in N$に対して,$x_i = x_j$$i,j$が同じグループに属していることを,$x_i \ne x_j$$i,j$が異なるグループに属していることを表すことにすると,次のように定式化することができます.

\[\begin{array}{@{}l@{\quad}l@{}} \max & \displaystyle \frac{1}{2} \sum_{i,j \in N, i<j} G_{ij}(1 - x_i x_j) \\ & s.t.\quad x_i \in \{-1,1\} \quad \forall i \in N \end{array}\]

 上記定式化に対し,変数$x_i, i \in N$$X_{ij} = x_i x_i$で置き換える変数$X_{ij}, i \in N, j \in N$を導入すると,次の問題と同値になることが知られています.

\[\begin{array}{@{}l@{\quad}l@{}} \max & \displaystyle \frac{1}{2} \sum_{i,j \in N, i < j} G_{ij}(1 - X_{ij}) \\ & \begin{array}{@{}l@{\quad}l@{}} s.t. & X \succeq 0 \\ & {\rm rank}(X) = 1 \\ & X_{ii} = 1 \quad \forall i \in N \end{array} \end{array}\]

 $x_i \in \{-1,1\}$は,$X_{ii}(= x_i x_i) = 1$に対応し,$x_i$$x_j$の値の整合性は$X \succeq 0$${\rm rank}(X) = 1$に対応します.ここで制約式${\rm rank}(X) = 1$を緩和した問題が次のSDP緩和問題となります.

\[\begin{array}{@{}l@{\quad}l@{}} \max & \displaystyle \frac{1}{2} \sum_{i,j \in N, i < j} G_{ij}(1 - X_{ij}) \\ & \begin{array}{@{}l@{\quad}l@{}} s.t. & X \succeq 0 \\ & X_{ii} = 1 \quad \forall i \in N \end{array}\end{array}\]

 上記定式化の目的関数を

\begin{align*} \frac{1}{2} \sum_{i,j \in N, i < j} G_{ij}(1 - X_{ij}) & = \frac{1}{4} \sum_{i,j \in N} G_{ij}(1 - X_{ij}) \\ & = \frac{1}{4} \sum_{i \in N} \left( \sum_{j \in N} G_{ij} X_{ii} - \sum_{j \in N} G_{ij} X_{ij} \right) \\ & = \frac{1}{4} ({\rm diag}(Ge) - G) \bullet X \end{align*}

と式変形をすることで以下の定式化が得られます.

集合
$N = \{ 1,2,3,4,5,6 \}$ ノードの集合
 
定数
$G_{ij}, i \in N, j \in N$ ノード$i \in N$とノード$j \in N$がつくるエッジの重みを表現する隣接行列
$L = diag(Ge) - G$ グラフ$G$のラプラス行列($e$は全ての要素が1のベクトル)
 
変数
$X_{ij}, i \in N, j \in N$ 緩和前ではノード$i \in N$とノード$j \in N$がカットされている場合に-1,カットされていない場合に1をとる変数
 
目的関数(最大化)
$\displaystyle \frac{1}{4}L \bullet X$ 緩和前ではカットされるエッジの重みの総和
 
制約
$X \succeq 0$ 半正定値制約
$X_{ii}=1, \forall i\in N$ 対角要素は1

 次に,行列をデータファイルから与えるSIMPLEモデルを示します.以下のモデルでは不要な変数を可能な限り消去するため,変数を上三角部分しか定義していないモデルになります.

// 集合と添え字
Set N;
Element i(set=N);
Element j(set=N);

// 行列パラメータ
Matrix G((i,j)); // 重み付き隣接行列
Matrix L((i,j)); // グラフ G のラプラス行列
L = diag(G*ones(N)) - G;

Set NN(dim=2); // 上三角部分
NN = setOf((i,j), i<=j);
Element ij(set=NN);

//変数
Variable x(index=ij);
SymmetricMatrix X((i,j));
X[i,j] = x[i,j], i<=j;
X[j,i] = x[i,j], i<j;
x[i,i] == 1; // 対角要素は 1
X >= 0;      // 半正定値制約

// 目的関数
Objective obj(type=maximize);
obj = 0.25 * inprod(L,X);

// 求解
solve();

// 出力
obj.val.print();

 データファイル(.csv形式)は以下のようになります.

G, 1, 2, 3, 4, 5, 6
1, 0, 2, 3, 0, 1, 3 
2, 2, 0, 1, 2, 0, 0 
3, 3, 1, 0, 2, 0, 3 
4, 0, 2, 2, 0, 1, 4 
5, 1, 0, 0, 1, 0, 2 
6, 3, 0, 3, 4, 2, 0

 このモデルを実行すると,目的関数値18.7437が得られます.これは最大化問題の緩和問題ですので,本問題の上界値となります.

 次に0-1整数計画問題としての定式化を紹介します.SDP緩和問題で得られた上界値の精度を調べてみましょう.

 まず変数は,各ノードに対し0-1変数$x_i, (i \in N)$を用意して「2つのグループに分割する」を「0の値をとるグループ」と「1の値をとるグループ」に対応させます.また,ノード$i$とノード$j$が異なるグループのときに1をとり,同じグループのときに0をとる変数$y_{ij}, (i \in N, j \in N)$を用意します.このとき,目的関数はカットされたエッジの重みの総和ですから,$\displaystyle \sum_{i<j} G_{ij} y_{ij}$で表現されます.注意するべきこととして$x_i$$y_{ij}$の整合性をとる制約を追加する必要があります.具体的に$(x_i, x_j, y_{ij}) = (0,1,1), (1,0,1), (0,0,0), (1,1,0)$となる組合せを残せばよいので,この組合せの補集合を考えて$(x_i, x_j, y_{ij}) = (0,1,0), (1,0,0), (0,0,1), (1,1,1)$となる組合せを排除する制約を導入します.このような制約を導入した定式化は次のようになります.

集合
$N = \{ 1,2,3,4,5,6 \}$ ノードの集合
 
行列
$G_{ij}, i \in N, j \in N$ ノード$i \in N$とノード$j \in N$がつくるエッジの重みを表現する隣接行列
 
0-1変数
$x_i, i \in N$ 0-1の2つのグループのどちらに入るかを表す変数
 
変数
$y_{ij}, i \in N, j \in N$ カットされたエッジの情報を$x_i, x_j$から得るための変数
 
目的関数(最大化)
$\displaystyle \sum_{i<j} G_{ij} y_{ij}$ カットされるエッジの重みの総和
 
制約
$-x_i - x_j + y_{ij} \le 0\quad (1)$ $(x_i, x_j, y_{ij}) = (0,0,1)$の排除
$-x_i + x_j - y_{ij} \le 0\quad (2)$ $(x_i, x_j, y_{ij}) = (0,1,0)$の排除
$x_i - x_j - y_{ij} \le 0\quad (3)$ $(x_i, x_j, y_{ij}) = (1,0,0)$の排除
$x_i + x_j + y_{ij} \le 2\quad (4)$ $(x_i, x_j, y_{ij}) = (1,1,1)$の排除

 上記にて変数$y_{ij}$は連続変数として定義されていますが,実際には0-1しかとらない変数となります.これは,式(1)(4)より$y_{ij} \ge 0$が,式(2)(3)より,$y_{ij} \le 1$が導かれ,さらに$(x_i, x_j)$の組合せが$(0,0), (0,1), (1,0), (1,1)$しかとらないことと式(1)(2)(3)(4)から,$y_{ij} = 0\ or\ 1$が導かれます.また,上記の不必要な組合せを排除する方法の代用として0-1変数$z_{ij}$を追加して,

\[x_i + x_j + y_{ij} = 2z_{ij}\]

と表現する方法もあります.次に,SIMPLEモデルを示します.以下のモデルでは不要な変数を可能な限り消去するため,変数を上三角部分しか定義していないモデルになります.

// 集合
Set N;
Element i(set=N);
Element j(set=N);

// 定数
Matrix G((i,j));

Set NN(dim=2); // 対角成分
NN = setOf((i,j),i<j);
Element ij(set=NN);

// 変数
IntegerVariable x(index=i,type=binary);
Variable y(index=ij); 

// x[i] x[j] y[i,j] の整合性をとる制約
- x[i] - x[j] + y[i,j] <= 0,(i,j)<NN; 
- x[i] + x[j] - y[i,j] <= 0,(i,j)<NN; 
  x[i] - x[j] - y[i,j] <= 0,(i,j)<NN; 
  x[i] + x[j] + y[i,j] <= 2,(i,j)<NN; 

// 目的関数
Objective obj(type=maximize);
obj = sum(G[ij]*y[ij],ij);

// 大規模問題には以下の近似解法を用いる
// ※ その際,y を 0-1 整数変数にする必要がある
// options.method="wcsp";

// 求解
solve();

// 出力
x.val.print();
obj.val.print();

 このモデルを実行すると,目的関数値18,ノード1,4,5のグループとノード2, 3, 6のグループが得られます.SDP緩和問題で求められた目的関数値が18.7437であったことを考えると,SDP緩和問題が非常に良質な上界値を与えていることがわかります.

 上記のようにSDP緩和問題で良質な上界値を得られることがわかっていれば,上界値を用いてWCSPアルゴリズムの精度保証に利用したり,終了条件を設定する際に利用したりもできます.参考までにSDP緩和問題,単体法(+分枝限定法),WCSPでそれぞれ解いた結果を以下に示します.以下の表はSDP緩和の上界値の精度と近似解法WCSPの安定性を示す十分な結果を表しています.

  SDP SIMPLEX WCSP
Graph TIME Upper TIME Optimal TIME Lower
G20.csv 0.2 464.39 0.2 452 0.05 452
G30.csv 1.2 825.64 1.2 797 2.1 797
G40.csv 6.5 1215.86 6.0 1164 1.7 1164
G50.csv 23.1 1736.33 23.7 1651 7.6 1651
G60.csv 55.5 2156.71 153.2 2068 27.4 2068
# GraphデータG**.csvの「**」はノード数を表す.上記データはすべてノードに対して平均10のリンクが存在するように乱数を発生させたデータ.
# WCSPアルゴリズムの設定は,最大探索時間10秒,乱数を用いた3回の探索試行を行った.

 

 

上に戻る