最小カット勉強会

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 1 0^{6}$ で、Dijの計算に * 100 だから $1 0^{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 1 0^{30}$
仮に1秒で $1 0^{10}$ 回の計算ができる機械を使ったとしても $3 \times 1 0^{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} \leq 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 (C V^{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つの三択として扱えば素直にそれぞれの選択肢でのコストの形になる
おそらく論理式による表現に慣れた我々が問題を見てまず論理式で表現してしまい、それから最小カットに変換しようとするところに問題がある
- 一般の論理式から最小カットへの変換は存在しないと思う
- そうではなく問題を最初から最小カットで表現する必要がある
- これは「論理式を考えてからそれをニューラルネットにするのではない」「論理式を考えてからそれをハミルトニアンにするのではない」ににた構図

🪴 Quartz 4.0

最小カット勉強会

Graph View

Backlinks