An introduction to network flow problems and algorithms

交通網，通信網，ライフラインなど現実世界のネットワークでは，車両，データ，水，電気，ガスなどを効率的に流すことを求める場合が少なくありません．この問題はグラフの辺に沿って「もの」を効率的に流すネットワークフロー問題に定式化できます．多くのネットワークフロー問題は線形計画問題に定式化できるため，単体法や内点法を適用すれば効率的に最適解を求めることができます．しかし，グラフの構造を利用すれば，より簡単で効率的なアルゴリズムを開発できる場合があります．今回は，そのようなネットワークフローの問題として，最大流問題と最小費用流問題を紹介します．

Transcript

1. 最⼤流問題と最⼩費⽤流問題 ⼤阪⼤学 ⼤学院情報科学研究科 梅⾕ 俊治 2022年4⽉27⽇
2. ネットワークフロー問題 • 交通網，通信網，ライフラインなど現実世界のネットワークで， ⾞両，データ，⽔，ガス，電気などを効率良く流す問題は，ネッ トワークフロー問題に定式化できる． • 多くのネットワークフロー問題は線形計画問題に定式化できるた め，単体法や内点法を⽤れば効率的に最適解を求められる． • ネットワークの持つ構造を利⽤することで，より効率的なアルゴ リズムを開発できる． ü最⼤流問題 → 増加路法，プリフロー・プッシュ法など ü最⼩費⽤流問題 → 負閉路消去法，最短路繰り返し法，ネッ トワーク単体法など ü割当問題 → ハンガリー法など 2
3. 最⼤流問題 • 有向グラフ ，各辺 の容量 が与えられる． • ⼊⼝ から出⼝ に流れるフローの総量 を最⼤にするには︖ ü⼊⼝ から流出する量＝出⼝ に流⼊する量 ü 以外の頂点 から流出する量＝頂点 に流⼊する量 ü各辺 の流量は容量 以下 3 * は頂点 を始点とする辺集合， は頂点 を終点とする辺集合． 流量保存制約 辺 の容量(定数) 辺 のフロー量(変数) フロー量 容量
4. 最⼤流の判定 • 最⼤流かどうかを効率良く判定するには︖ • ⼀部の辺でフローを押し戻す操作でフローの総量が増えることも多い． 4
5. 残余ネットワーク • 各辺の可能な残りフロー量を表すネットワーク． • 各辺 に対して逆向き辺 を⽤意し，押し戻しが 可能なフロー量を表す． • 増加路︓残余ネットワークの頂点 から頂点 にいたる路． ü増加路が存在する → フローの総量を増加できる ü増加路が存在しない → フローの総量は増加できない(最⼤流) 5 実⾏可能なフロー 残余ネットワーク
6. 増加路法 • 現在の実⾏可能フローに対する残余ネットワークを求める． • 増加路を1つ求めて実⾏可能フローを更新する*． 6 *グラフに対する幅優先探索などを⽤いれば増加路を求められる．
7. 増加路法 7 * 辺数， 頂点数， 容量の最⼤値． * 問題例の⼊⼒サイズは なので擬多項式時間アルゴリズムである． 増加路なし 反復回数 総流量の最⼤値 増加路を⾒つけるのに 時間 時間
8. s-t カット • 最⼤流を求める際のネットワークのボトルネックは︖ • カット ︓⼊⼝ を含み出⼝ を含まない頂点集合 のカット． • カット の容量︓ から に向かう辺の容量の総和． 8 フローの総量 より フローの総量 カットの容量 カット容量 45
9. 最⼤フロー最⼩カット定理 • 増加路法が最⼤流を求めることを⽰したい． • 残余ネットワークで頂点 から到達可能な頂点集合を とすると， は最⼩カットで 最⼤フローの総量 最⼩カットの容量 9 *辺の容量いっぱいにフローを流すと残余ネットワークでは逆向きの辺しか残らないことに注意する． 残余ネットワークにおいて から に向かう辺はない* 元のネットワークにおいて から に向かう辺では から に向かう辺では
10. 最⼩費⽤流問題 • 有向グラフ ，各辺 の容量 ，単位フロー量 当たりのコスト ，各頂点 から流出するフロー量 が与え られる*．総費⽤を最⼩にする実⾏可能なフローは︖ • 最短路問題，最⼤流問題は最⼩費⽤流問題の特殊ケース 10 * 頂点 にフローが流⼊するときは ．また， と仮定する． 費⽤ 容量 流出 辺 の容量(定数) 辺 の費⽤(定数) 頂点 の流出量(定数) 辺 のフロー量(変数) 流量保存制約 流⼊
11. 残余ネットワークを⽤いた最⼩費⽤流の判定 • 最⼩費⽤流かどうかを効率良く判定するには︖ • ⼀部の辺でフローを押し戻す操作で全体の費⽤が減ることも多い． • 残余ネットワークの負閉路に着⽬する． ü負閉路が存在する→フローの総費⽤を減少できる ü負閉路が存在しない→フローの総費⽤を減少できない(最⼩費⽤流) 11 フロー量 /容量 費⽤ 費⽤ 実⾏可能なフロー 残余ネットワーク 容量 費⽤
12. 負閉路消去法 • 現在の実⾏可能フローに対する残余ネットワークを求める． • 負閉路を1つ求めて実⾏可能フローを更新する． 12 *残余ネットワーク上の負閉路は，最短路問題に対するベルマン・フォード法などで求められる． ⾃明な初期実⾏可 能解を与えるため に頂点と辺を追加
13. 負閉路消去法 • 現在の実⾏可能フローに対する残余ネットワークを求める． • 負閉路を1つ求めて実⾏可能フローを更新する． 13 原問題の 初期実⾏可能フロー
14. 負閉路消去法 14 負閉路なし 反復回数 費⽤の最⼤値 負閉路を⾒つけるのに 時間 時間 * 費⽤の最⼤値．
15. (被約費⽤)とおくと 最短路繰り返し法 • 最⼩費⽤流問題は線形計画問題に定式化できる． • 主双対法︓双対問題の制約条件と相補性条件を満たしつつ， 主問題の制約条件の違反量を繰り返し減少して最適解を求める． 15 主問題 双対問題 相補性条件 主問題の実⾏可能解 と 双対問題の実⾏可能解 が 最適解となるための必要⼗分条件 反復のたびに違反量を減少
16. 最短路繰り返し法 最⼩費⽤流問題の最適性条件 最⼩費⽤流問題の実⾏可能なフロー が最適であるための必要 ⼗分は，残余ネットワークの全ての辺に対して となる が存在することである． 16 ある辺 において ならば， より ならば， より ならば， より . これらの条件の対偶より得られる． 最⼩費⽤流問題の相補性条件 最⼩費⽤流問題の実⾏可能なフロー が最適であるための必要⼗分 条件は，全ての辺 に対して となる が存在することである． 残余ネットワークでは逆向き 辺のみ残るので，全ての辺で が成り⽴つ ポテンシャルと呼ぶ
17. 最短路繰り返し法 • 流量保存制約を満たさない頂点間 の最短路にフローを流す． ⼿続きを繰り返す．ただし，辺 の⻑さを被約費⽤ とする． • 頂点 のポテンシャル を最短路の⻑さ だけ増やす． 17 違反量 容量 <latexit sha1_base64="BbILW5B3YDUC4WDhZTRcek8KlA4=">AAACvHichVHLSsNAFD3Gd3006kZwIxZFN2UiRcWFFNy4rNZawUpI4lRD8yJJKzX0B/wBF+JCQUX8DDfi3oWfIC4ruHHhTRoQldY7TObMmXvunMlVHUP3fMZeuoTunt6+/oHBxNDwyGhSHBvf8eyqq/GCZhu2u6sqHjd0ixd83Tf4ruNyxVQNXlQr6+F5scZdT7etbb/u8H1TObT0sq4pPlGyOFZSFTfQGjKfL6lmUG8syGKKpVkU03+BFIMU4sjZ4hNKOIANDVWY4LDgEzagwKOxBwkMDnH7CIhzCenROUcDCdJWKYtThkJshb6HtNuLWYv2YU0vUmt0i0HTJeU0Ztkzu2NN9sju2Sv7bFsriGqEXuq0qi0td+Tk6WT+41+VSauPo29VR88+yliJvOrk3YmY8BVaS187OWvmV7dmgzl2xd7I/yV7YQ/0Aqv2rl1v8q3zDn5U8tL+jwXElb/dUhul3037C3YW09JSOrOZSWUzcUMHMIUZzFPXlpHFBnIo0C3HuMANboU14UCoCGYrVeiKNRP4EULtC8m8n6E=</latexit> ¯ ce (y)
18. 最短路繰り返し法 • 流量保存制約を満たさない頂点間の最短路に沿ってフローを流す ⼿続きを繰り返す． 18 反復回数 違反量の総和 最短路を⾒つけるのに 時間 時間 更新されたポテンシャル の下での被約費⽤ 最短路の⻑さは三⾓不等式を満たすので したがって，常に が成り⽴つ． 違反なし
19. 割当問題 • ⼈の学⽣を 個のクラスに割り当てる．各クラス の受講者の 上限を ，各学⽣ を各クラス に割り当てたときの満⾜度を とする．学⽣の満⾜度を最⼤にするクラス編成は︖ 19 学⽣ をクラス に割り当てる(変数) 学⽣ クラス 学⽣ のクラス に対する満⾜度(定数) クラス の受講者数の上限(定数)
20. 割当問題→最⼩費⽤流問題 • 各学⽣に対応する頂点 ，各クラスに対応する頂点 • 頂点 から各学⽣ への辺 容量1, 費⽤0 • 各クラス から頂点 への辺 容量 ，費⽤0 • 各学⽣ から各クラス への辺︓容量1，費⽤ 20 学⽣ クラス 容量 費⽤ 実⾏可能流 定員を満たす割当て 実⾏可能流の費⽤ 学⽣の満⾜度の合計
21. 参考⽂献 • 久野誉⼈，繁野⿇⾐⼦，後藤順哉，数理最適化，オーム社，2012． • 繁野⿇⾐⼦，ネットワーク最適化とアルゴリズム，朝倉書店，2010． • R.A.Ahuja, T.L.Mangnanti and J.BOrlin, Network Flows: Theory, Algorithms, and Applications, Peason Education, 2014. 21