こんにちは！しゅんです！
今回の記事は2部グラフの最小重み完全マッチングついて解説していきます！
マッチングとはグラフ理論という数学の分野で登場する用語で、現実世界の様々な分野で応用できます。
マッチングには色々な種類がありますが、その中でも今回は完全グラフじゃない部グラフの最小重み完全マッチングを求める問題を整数計画問題として定式化してみたいと思います！
2部グラフの最小重み完全マッチングについてはこちらの記事で解説しています！
完全2部グラフの最小重み完全マッチングの定式化はこちらの記事で解説しています！
それではやっていきましょう！
普段は統計検定2級の記事を書いてたりします。
ぜひ他の記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
2パターンの定式化を考える
今回は2パターンの定式化を考えたいと思います。1つ目は「辺集合を中心に考える方法」で、2つ目は「辺の重みをめっちゃ大きくする方法」です。
この記事では「辺集合を中心に考える方法」について解説したいと思います！
「辺の重みをめっちゃ大きくする方法」についてはこちらの記事で解説しています！
現在制作中
具体例を使って考える
今回は以下の2部グラフにおける最小重み完全マッチング問題を整数計画問題として定式化したいと思います。
このグラフは左右の頂点が3つずつある2部グラフです。このグラフには辺\((0,2)\)と辺\((1,1)\)がないので完全グラフではありません。
それではこのグラフの最小重み完全マッチング問題を整数計画問題として定式化するために「変数」、「目的関数」、「制約条件」の3つを考えていきましょう。
変数の設定
まず最初に変数の設定をしていきましょう。頂点\(i\)を左側の頂点、頂点\(j\)を右側の頂点とするとき、今回は以下の変数\(x_{ij}\)を使います。
\(x_{ij}= \left\{\begin{array}{lr} 1 \;\;\; \text{辺}(i,j)\text{を採用する} \\ 0 \;\;\; \text{辺}(i,j)\text{を採用しない} \end{array} \right.\)
ただし今回は辺\((0,2)\)と辺\((1,1)\)がないので\(x_{02}\)と\(x_{11}\)はありません。
例えば上の具体例だと各変数\(x_{ij}\)は以下のようになります。
\(x_{01}=x_{12}=1\)
\(x_{00}=0\)
\(x_{10}=0\)
\(x_{20}=0\)
\(x_{21}=0\)
\(x_{22}=0\)
\(x_{00}=x_{12}=x_{21}=1\)
\(x_{01}=0\)
\(x_{10}=0\)
\(x_{20}=0\)
\(x_{22}=0\)
目的関数の設定
次に目的関数を設定します。今回は最小重みマッチングを求めたいので、採用した辺の重みの合計を目的関数とします。これを変数\(x_{ij}\)を使って表すと以下のようになります。
\(3x_{00}+2x_{01}+x_{10}+4x_{12}+2x_{20}+x_{21}+3x_{22}\)
例えば上の具体例だと目的関数はそれぞれ以下のようになります。
\((3\times 0)+(2\times 1) + (1\times 0)+(4\times 1)\)
\(+(2\times 0)+(1\times 0)+(3\times 0)\)
\(=2+4=6\)
\((3\times 1)+(2\times 0) + (1\times 0)+(4\times 1)\)
\(+(2\times 0)+(1\times 1)+(3\times 0)\)
\(=3+4+1=8\)
マッチングとして採用されない辺\((i,j)\)の変数\(x_{ij}\)は0になるので、目的関数のその部分は0となります。そのため最終的に足される値はマッチングとして採用された辺の重みとなる訳です。
制約条件の設定1 : 左側の頂点
それでは最後に制約条件を設定しましょう。まず最初に左側の頂点0について考えてみましょう。
左側の頂点0は右側のいずれか1つの頂点と結ばれる必要があります。上の図の左側の例がOKな例です。
一方で例えばどの右側の頂点とも結ばれない、頂点0が2つの頂点と結ばれている場合はマッチングにはなりません。このNGな例を作らないように制約条件を設定する必要があります。
左側の頂点0に関する変数は\(x_{00},x_{01}\)の2つですが、これらのうちどっちか1つが1になってもう1つが0になればOKです。ということで左側の頂点0に関する制約条件は以下のようになります。
左側の頂点0に関する制約：
\(x_{00}+x_{01}=1\)
またこの条件は左側の頂点1、２に対しても成立する必要があります。頂点1に関する変数は\(x_{10},x_{12}\)、頂点2に関する変数は\(x_{20},x_{21},x_{22}\)なので制約条件はそれぞれ以下のようになります。
左側の頂点1に関する制約：
\(x_{10}+x_{12}=1\)
左側の頂点2に関する制約：
\(x_{20}+x_{21}+x_{22}=1\)
制約条件の設定2 : 右側の頂点
次に右側の頂点について考えましょう。実は左側の頂点に関する制約を考えただけでは条件が足りないんです。上の図は左側の頂点に関する制約条件を全て満たすあるグラフです。
確かにこのグラフの左側の頂点を見るとちゃんと1つの辺と接続していますね。しかし右側の頂点を見てみると、頂点0は2つの辺と接続しているので、これではマッチングにはなりません。
そういった理由で右側の頂点に関しても制約条件を付け足す必要があります。右側の各頂点に関する制約条件は以下のようになります。
右側の頂点0に関する制約：
\(x_{00}+x_{10}+x_{20} = 1\)
右側の頂点1に関する制約：
\(x_{01}+x_{21} = 1\)
右側の頂点2に関する制約：
\(x_{12}+x_{22} = 1\)
整数計画問題としてまとめる
それでは最後にここまで話してきたことをまとめて整数計画問題として定式化しましょう。
定式化1：
\( \min \;\;\; 3x_{00}+2x_{01}+x_{10}+4x_{12}+2x_{20}+x_{21}+3x_{22}\)
\(\; \text{s.t.} \;\;\;\;x_{00}+x_{01}=1\)
\(\;\;\;\;\;\;\;\;\;\;x_{10}+x_{12}=1\)
\(\;\;\;\;\;\;\;\;\;\;x_{20}+x_{21}+x_{22}=1\)
\(\;\;\;\;\;\;\;\;\;\;x_{00}+x_{10}+x_{20}=1\)
\(\;\;\;\;\;\;\;\;\;\;x_{01}+x_{21}=1\)
\(\;\;\;\;\;\;\;\;\;\;x_{12}+x_{22}=1\)
\(\;\;\;\;\;\;\;\;\;\;x_{ij}\in \{0,1\}\;\;\;\;(i = 0,1,2\;j = 0,1,2)\)
これで一応定式化はできたんですけど結構見づらいですよね。ということでいくつか文字を導入してもう少し簡潔に表記したいと思います。
もう少し簡潔に表す
まず最初に辺集合\(E\)を定義します。
\(E=\{(0,0),(0,1),(1,0),(1,2),(2,0),(2,1),(2,2)\}\)
次に辺\((i,j)\)の重みを\(w_{ij}\)と表します。例えば辺\((i,j)=(0,0)\)の重みは3なので\(w_{00}=3\)となります。これを使って目的関数を書き換えると以下のように表すことができます。
\(\sum\limits_{(i,j) \in E} w_{ij}x_{ij}\)
\(\sum\)の下に\((i,j) \in E\)と書いてありますが、これは「集合\(E\)中の全ての要素\((i,j)\)に関して足し算してください」ということを表しています。
さらに制約条件も\(\sum\)を使うと以下のように表せます。
左側の頂点：
\(\sum\limits_{(i,j) \in E} x_{ij}=1 \;\;\;\; (i = 0,1,2)\)
右側の頂点：
\(\sum\limits_{(i,j) \in E} x_{ij} = 1 \;\;\;\; (j = 0,1,2)\)
ということでこれらをまとめると最小重み完全マッチングを以下のように整数計画問題として定式化できます。
定式化2：
\(\min \;\;\; \sum\limits_{(i,j) \in E} w_{ij}x_{ij}\)
\(\;\text{s.t.}\;\;\;\sum\limits_{(i,j) \in E} x_{ij}=1 \;\;\;\; (i = 0,1,2)\)
\(\;\;\;\;\;\;\;\;\;\sum\limits_{(i,j) \in E} x_{ij} = 1 \;\;\;\; (j = 0,1,2)\)
\(\;\;\;\;\;\;\;\;\; x_{ij} \in \{0,1\} \;\;(i=0,1,2 \; j=0,1,2)\)
より一般的に考える
それではこれまでの具体例を踏まえてより一般の2部グラフの最小重み完全マッチングを定式化してみましょう。
上の2部グラフ\(G=(V_1,V_2,E)\)は\(V_1\)が左側の頂点集合、\(V_2\)が右側の頂点集合、\(E\)が辺集合をそれぞれ表しています。
このグラフに対して、最小重み完全マッチングを求める問題を整数計画問題として定式化していきましょう。
変数の設定
まず最初に定式化するために必要なパラメータや変数を設定しましょう。まず辺\((i,j)\)の重みを\(w_{ij}\)とします。また辺\((i,j)\)をマッチングとして採用するなら1、そうでないなら0を取るような変数を\(x_{ij}\)とします。
\(w_{ij}\) : 辺\((i,j)\)の重み
\(x_{ij}\in\{0,1\}\) : 辺\((i,j)\)を採用するなら1、そうでないなら0
目的関数の設定
次に目的関数の設定をしましょう。辺集合\(E\)が与えられているので\(E\)中の全ての要素\((i,j)\)に対して\(w_{ij}x_{ij}\)を足したものが最小になることを考えればよいです。
\( \sum\limits_{(i,j) \in E} w_{ij}x_{ij}\)
制約条件の設定
最後に制約条件を設定します。具体例の時は\(i=0,1,2 \; j=0,1,2\)のときを話していましたが、左側の頂点集合が\(V_1\)、右側の頂点集合が\(V_2\)なので\(\forall i \in V_1 \; \forall j \in V_2\)とすれば良いです。
左側の頂点：
\(\sum\limits_{(i,j) \in E} x_{ij}=1 \;\;\;\; (\forall i \in V_1)\)
右側の頂点：
\(\sum\limits_{(i,j) \in E} x_{ij} = 1 \;\;\;\; (\forall j \in V_2)\)
整数計画問題としてまとめる
最後にこれらをまとめて整数計画問題として定式化しましょう。
定式化：
\(\min \;\;\; \sum\limits_{(i,j) \in E} w_{ij}x_{ij}\)
\(\;\text{s.t.}\;\;\;\sum\limits_{(i,j) \in E} x_{ij}=1 \;\;\;\; (\forall i \in V_1)\)
\(\;\;\;\;\;\;\;\;\;\sum\limits_{(i,j) \in E} x_{ij} = 1 \;\;\;\; (\forall j \in V_2)\)
\(\;\;\;\;\;\;\;\;\;\;\; x_{ij} \in \{0,1\} \;\;(\forall (i,j) \in E)\)
次回の記事では定式化した整数計画問題をpythonで表現して実際に問題を解いてみたいと思います！
次回の記事はこちらから！
現在制作中
おわりに
いかがでしたか。
今回の記事では完全グラフじゃない2部グラフの最小重み完全マッチングについて解説していきました。
今後もこのような数理最適化に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
