最小カット勉強会

NISHIO Hirokazu [Translate]
最小カット勉強会
2021-03-19 サイボウズラボ勉強会
ある種の最適化問題を解くときに使える「最小カット問題に帰着させて解く」を解説する

簡単な最適化問題
二択の選択肢がN個ある
選択肢を1つ選ぶと100円もらえる
しかし選ぶのにCi円のコストが掛かる
利益を最大にする選択は？

解答
利益 100 - Ci が正のものを選ぶ

簡単な最適化問題2
二択の選択肢がN個ある
選択肢を1つ選ぶと100円もらえる
しかし選ぶのにCi円のコストが掛かる
選択肢をM個選ぶ場合の利益を最大にする選択は？

解答
ソートして利益の大きい方からM個取る

一歩進んだ問題
二択の選択肢がN個ある(N=20)
選択肢を1つ選ぶと100円もらえる
しかし選ぶのにCi円のコストが掛かる
ある選択肢iを選んで選択肢jを選ばなかった場合、追加でDijのコストが掛かる
非ゼロのコストはM個(M=100)
利益を最大にする選択は？

解答
2^N通り全探索する
2^{20} = 1048576 \approx 10^6で、Dijの計算に * 100 だから 10^8回くらいの計算 
Python3  11.3 s ± 173 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 
PyPy3  1.1 s ± 37 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 
spec


今回解く問題
二択の選択肢がN個ある(N=100) ←🤔
選択肢を1つ選ぶと100円もらえる
しかし選ぶのにCi円のコストが掛かる
ある選択肢iを選んで選択肢jを選ばなかった場合、追加でDijのコストが掛かる
非ゼロのコストはM個(M=100)
利益を最大にする選択は？

全探索だとどうなる？
2^{100} \approx 10^{30}
仮に1秒で10^{10}回の計算ができる機械を使ったとしても3\times 10^{12}年かかる

解答
最小カット問題に帰着し、最大フロー最小カット定理で最大フロー問題に変換してDinicアルゴリズムで解く
かなり速い
N=M=100の時は1ミリ秒未満だった
1000回繰り返した時間
Python3  858 ms ± 222 ms per loop (mean ± std. dev. of 5 runs, 1000 loop each) 
PyPy3  214 ms ± 139 ms per loop (mean ± std. dev. of 7 runs, 1000 loop each) 
N=M=10000でも0.2秒くらい
Python3  243 ms ± 40 ms per loop (mean ± std. dev. of 5 runs, 1 loop each) 
PyPy3  114 ms ± 45 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 
N=M=100000で、PyPyなら1〜2秒ぐらい
PyPy3  1.4 s ± 172 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

カットとは
>グラフ G(V, E) の頂点 V の 2 分割 (S, T) をカットとよぶ。
「頂点の集合」を二つに分けるだけ
物理的なイメージとしては「二色に塗り分ける」がフィットする
カットという言葉に釣られて「グラフを二つに切る」と考えるのは混乱の元
辺は関係ない
これもカットです
世の中にはここで「フローがどうこう」と言っちゃう説明文もあるけど、フローを考えるのはもっと後の「最小カットを最大フローに対応づける」フェーズで良いので、ここでは気にしない
この段階でフローのことを考えるのも混乱の元。上記のカットに対応するフローはないので。

最小カット問題とは
(今回は有向グラフの話しかしない)
有向グラフG = (V, E) のカット (S, T)が与えられた時、Gの辺 (u, v) \in Eのうち u \in S, v \in Tであるものをカットエッジという。
カットエッジの重みの和をカットのサイズといい、サイズが最小のカットを最小カットという。
しばしば「Sに必ず入る頂点s」「Tに必ず入る頂点t」を考えると都合がいい。sとtがそうなるようなカットを「s-tカット」と呼んだりする。
Q: 根本がTで先がSであるような辺はカットエッジではない？
A: 良い質問、次のスライドで理解の確認をする

最小カットの理解の確認
このグラフのs-t最小カットはどうなるでしょう？
(注釈: 元々の図では頂点を大文字で書いていたが、頂点集合Sと頂点sを区別するために小文字に変えた)


解答
a \in T, b \in Sのときカットサイズが3で最小になる
カットを「グラフを切る」とイメージしてると「真ん中の5の辺」を切らないでいいのかとか混乱しがち
根本がTで先がSであるような辺なので、カットのサイズに無関係である
頂点を二色で塗り分ける方法がsとtは固定なので4通りある
a \in S, b \in Tの時は15
両方Sや、両方Tの時は6
なので3が最小
最小カットのカットは「辺を切る」ではない
カット=頂点の二色塗り分け

最小カットに帰着
再掲
>最小カット問題に帰着し、最大フロー最小カット定理で最大フロー問題に変換してDinicアルゴリズムで解く
「最小カット問題とは何か」の説明が終わった
次は下記の問題をどうやって最小カット問題に帰着するか説明する
>二択の選択肢がN個ある(N=100) ←🤔
>選択肢を1つ選ぶと100円もらえる
>しかし選ぶのにCi円のコストが掛かる
>ある選択肢iを選んで選択肢jを選ばなかった場合、追加でDijのコストが掛かる。非ゼロのコストはM個(M=100)
>利益を最大にする選択は？
利益を最大にしたい=コストを最小にしたい
コストを辺の重みにすると、最小カットでコスト最小化できる
「選択肢iを選ぶ」を「頂点iをSに入れる」とした場合
「選ぶとコストCi」とは
頂点iから頂点tに重みCiの辺を引く

「選ぶと報酬100」とは
報酬は負のコストなので、頂点iから頂点tに重み-100の辺を引く
(後で負辺の除去が必要になるが今は考えなくて良い)
「iを選んでjを選んでないとコストDij」
頂点iから頂点jに重みDijの辺を引く
このグラフの最小カットを求めれば、得たい答えが得られる

具体例
3つの二択選択肢a,b,cがある
選択すると100の報酬がある
選択することにそれぞれ10,70,150のコストが掛かる
aを選んだ時にcを選ばないと追加コスト40が掛かる
構築されるグラフ
Q: 「sが分離してていいのか？自明にそこが最小カットになる？」
A: 負の重みの辺があるのでそれが最小解とは限らない
この混乱は「カット」を「グラフを2つに分ける」と混同していることが原因
次のスライドからこの最小カット問題を最大フロー問題に変換する。その過程でsがつながってフローを考えるのに適したグラフになる

次は何をやる？
再掲
>最小カット問題に帰着し、最大フロー最小カット定理で最大フロー問題に変換してDinicアルゴリズムで解く
最小カット問題に帰着できた
次は最大フローに変換する

最大フロー問題
辺の重みが非負のグラフG=(V,E)が与えられたとする
この重みをフローの文脈では「容量」と呼ぶ
このグラフの二頂点s, tの間のフローを考える
sからtに水を流すイメージ
最大限流したときにいくら流れるか？が最大フロー問題
G上のフローとは重み付きグラフ(V,F)であって:
各辺の重みはGでの容量を超えない: F_{ij} \le E_{ij}
s,t以外の頂点iについて入るフローと出るフローが一致する: \sum_j F_{ji} = \sum_j F_{ij}

最大フロー最小カット定理
辺の重みが非負のグラフのs-t最小カットのサイズと、sからtへの最大フローの流量は一致することが知られている
今回は証明はしない
see 塩浦昭義 数理計画法 第8回
ざっくりしたイメージ
sからtへの最大フローFの流量をGの容量から減らしたグラフ(残余ネットワーク)を考えると、これは必ず2つ以上の連結成分に別れている
もしそうでないならさらにフローを増やすことができて前提に矛盾する(図中のe)
「グラフの頂点を二つに分ける」はカットで、フローを最大化すると、最小のカットの部分がボトルネックになる

負辺の除去
最小カット問題を最大フロー問題に変換して解く
最大フロー問題では辺の容量は非負である必要があるので、負の辺を取り除く必要がある
ある頂点iに注目すると、その頂点はSに入るかTに入るかのどちらか
なのでSに入ったときにもTに入ったときにも同額の追加コストcが掛かるようにする
これで負辺が消える
変更後のグラフの最小カットサイズはc増える
負辺除去の過程で足した値の和(offset)を記録しておいて、答えが出てから引く
実例
負辺の除去
最小カットは-80

(自由な頂点間の負辺の除去は後述)

Dinicアルゴリズム
グラフの最大フローを求める効率の良いアルゴリズム
古典的なFord-Fulkersonを少し改良したもの
(といってもDinicも1970年なので古典の域か)
詳しい説明は今回はしない see: Slide by 郭至軒
辺の重みが非負の有向グラフと始点s終点tを入れるとs-t最大フローが出てくる
これが最小カットのサイズに一致する
最大フロー計算後に内部に持ってる残余ネットワーク上で探索して各頂点のsから到達可能な頂点を求めればそれが最小カットのSになる

Dinicの計算量
Dinicの計算量はO(V^2E)とされている
しかし探索ベースの手法なので10^4頂点10^4辺でも必ず10^12回計算するわけではない
先程の問題でN=M=10000の時、グラフは10002頂点、20000辺になる
これが114msで計算できた
どのくらいのサイズの問題まで解けるのか？
N=10000固定で、Mを増やして試したもの(横軸M、縦軸ms) data
この範囲ではほぼ線形(ちょっと悪い？)
これはV固定でEを増やしてるので線形なのは理屈通り
N=Mの条件でNを動かして観察 data
計算量的にはN^3なのだが、実測は線形に見える
おそらく「この最適化問題から作られるグラフ」が「Dinicに都合の良い特徴」を持ってるのだろう
Dinicの速さ: 辺の重みが整数である時にはいろいろな条件で計算量が下がる
この実験では各コストを「1から200のランダムな整数」としているので辺の重みが整数でかつ上限がある
この場合、上限をCとしてO(CV^{2/3}E)


応用
「iを選んだ時、jを選ばなければならない」型の制約
i→jを十分大きなコストにすればよい
and: 「iを選んだなら、jとkを選ばなけれはならない」
or: 「iまたはjが選ばれたなら、kを選ばなければならない」

Project Selection Problem
ここまでの知識でProject Selection Problemと呼ばれるタイプの問題が解ける
N個のプロジェクトがある
プロジェクトiをやると収入r_iが得られる
M個の機械がある
機械jを買うとコストc_jが掛かる
プロジェクトをやるためにはそのプロジェクトに必要な機械を買わなければならない
利益=収入-コストを最大化するにはどのプロジェクトを選べば良いか？


応用の続き
not
「iを選んだ時、jを選んではいけない」
これは一般にいつでもできるわけではない
iを選ぶことをiをSに入れることで表現し、jを選ぶことをjをTに入れることで表現する
こうすれば上記の制約を表現できるが、事前に「選択されたときにどちらに入るのか」を決める必要がある
この時、上記の制約は「選択されたときにSに入る頂点」と「選択された時にTに入る頂点」の間にしかかけられない
一言で言えば「二部グラフ」
1列に並んだものや2次元のマス目の隣接関係
交互にSとTにすればよい
マス目を塗る問題で、隣り合うマス目を塗るとコストが発生するケースなどにこれを使う

二択以上の選択肢
できる
三択の例
同様にN択を、N-1個の頂点を並べて表現できる
同様に実数値の変数に対して「iがx以上なら、jはy以上でなければならない」もできる

自由な頂点間の負辺除去
こういうタイプの負辺はどう除去するのか
多分このままだと無理
jを「選んだときにT」の頂点j'に変える

逆向きに無限大辺がついてる場合はもっと簡単
「十分に大きな重み」をもっと大きくしても問題がないため


まだ僕がわかってないこと
「iとjがSなら、kもS」という形のandはできるか？
「iがSなら、jまたはkがS」という形のorはできるか？
n択を表現するのに使ったような方法で中間レイヤーを挟んで解決できないのか？
たとえばN個の対象に二択の選択肢(0/1)が二つ(A, B)あるケースで、「Ai=1かつBi=0ならコストc」「Ai=1かつBi=1ならコストd」「Ai=0ならコストe」というパターン
これを2つの二択だと考えているとandをどう実現するかで悩む
1つの三択として扱えば素直にそれぞれの選択肢でのコストの形になる
おそらく論理式による表現に慣れた我々が問題を見てまず論理式で表現してしまい、それから最小カットに変換しようとするところに問題がある
一般の論理式から最小カットへの変換は存在しないと思う
そうではなく問題を最初から最小カットで表現する必要がある
これは「論理式を考えてからそれをニューラルネットにするのではない」「論理式を考えてからそれをハミルトニアンにするのではない」ににた構図