数理最適化セミナーのご案内

2.23 最大カット問題

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

　この問題は，半正定値計画（SDP）との関連が知られています．

例題

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

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

　この問題をNuorium Optimizerで解くために定式化を行います．まずはSDP緩和問題として定式化し，目的関数値の上界値を求めてみましょう．以下で紹介する定式化は参考文献[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_j$で置き換える変数$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$は$(X_{ij})_{i,j \in N}$からなる行列を表し，${\rm rank}(X)$は行列の階数，$X \succeq 0$は行列$X$が半正定値であることを表します．上式において$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}\]

　もとの二次計画問題の定式化の詳細は以下になります．

集合
$N = \{ 1, 2, 3, 4, 5, 6 \}$ ノードの集合
　
定数
$G_{ij}, i \in N, j \in N$ グラフのエッジ$(i,j)$の重み
　
変数
$x_{ij} \in \{-1, 1\}, i \in N, j \in N$ ノード$i \in N$が一方のグループに含まれている場合1，もう一方のグループに含まれている場合-1
　
目的関数（最大化）
$\displaystyle \frac{1}{2} \sum_{i, j \in N, i<j} G_{ij}(1 - x_i x_j)$ カットされるエッジの重みの総和

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

// 集合と添字
Set N;
Element i(set = N);
Element j(set = N);
Set NN(dim = 2); // 上三角部分
Element ij(set = NN);

// パラメータ
Parameter G(index=(i, j)); // 重み付き隣接行列

NN = setOf((i, j), i <= j);

// 変数
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.5 * sum(G[i,j] * ( 1 - X[i,j]), ((i,j), i<j));

// 求解
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} \le 1$が，式(2)(3)より，$y_{ij} \ge 0$が導かれ，さらに$(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}\]

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

// 集合と添字
Set N;
Element i(set = N);
Element j(set = N);
Set NN(dim = 2);
Element ij(set = NN);

// パラメータ
Parameter G(index=(i, j));

NN = setOf((i, j), i < j);

// 変数
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回の探索試行を行った．
2.22 ロバストポートフォリオ最適化問題
2.24 セミナー割当問題

 

 

上に戻る