この記事について
前回①では最短路問題をLPで解いて、フロー保存則という道具を手に入れました。今回は同じ道具で 最大流問題（maximum flow problem） を解きます。
やることはほとんど変わりません。 目的関数と制約をちょっと書き換えるだけ で、まったく別の問題が解けてしまいます。ここがフローの枠組みの強いところです。
ネットワーク最適化入門シリーズの他の記事はこちら。
第1部：定式化編（LP・整数計画で解く）
| 記事 | 内容 |
|---|---|
| ① | ネットワーク最適化とは？最短路をLPで解く |
| ②（本記事） | 最大流問題をLPで解く |
| ③ | 最小カットと最大流最小カット定理 |
| ④ | 最小費用流問題 ─ ネットワーク問題の親玉 |
| ⑤ | 割当問題・マッチング ─ なぜ整数解が出るのか |
| ⑥ | 資源制約付き最短路 ─ 整数性が壊れる瞬間 |
| ⑦ | Steiner木問題 |
| ⑧ | 多品種流問題 |
第2部：アルゴリズム編（専用アルゴリズムで解く）
| 記事 | 内容 |
|---|---|
| ⑨ | ダイクストラ法 |
| ⑩ | ベルマン-フォード法と負閉路 |
| ⑪ | Yenのアルゴリズムで K 本の最短路を列挙 |
| ⑫ | フォード・ファルカーソン法と最小カットの取り出し |
| ⑬ | 逐次最短路法で最小費用流を解く |
| ⑭ | ハンガリアン法 |
| ⑮ | Steiner木の2近似アルゴリズム |
| ⑯ | 多品種流のラグランジュ緩和＋シリーズまとめ |
最大流問題とは
「始点 A から終点 F へ、容量を超えない範囲で最大どれだけ流せるか」
という問題です。①では「1単位だけ流して、その費用を最小に」でしたが、今回は 費用は無視して、とにかく量を最大に します。
現実の例だと、
- 水道管のネットワークで、水源から街へ最大何トン送れるか
- 通信ネットワークで、拠点間の最大スループットはいくらか
- 道路網で、朝のピーク時に何台さばけるか
みたいな話です。
前回と同じネットワークを使います。今回は 容量（スラッシュの右側）だけ に注目してください。
定式化
①との違い
まず①と何が変わるかを整理します。
| ① 最短路 | ② 最大流（本記事） | |
|---|---|---|
| 目的関数 | $\sum c_a x_a$ を最小化 | 流量 $F$ を最大化 |
| 枝の上限 | なし | $f_a \le u_a$（容量制約） |
| 湧き出し量 $b_v$ | $+1 / -1 / 0$ で固定 | $+F / -F / 0$（$F$ も変数） |
| 費用 $c_a$ | 使う | 使わない |
「湧き出し量そのものを変数にして、それを最大化する」 というのがポイントです。
式で書く
決定変数は各枝の流量 $f_a \ge 0$ と、全体の流量 $F$ です。
\begin{aligned}
\text{最大化} \quad & F \\
\text{条件} \quad & \sum_{a \in \delta^+(v)} f_a - \sum_{a \in \delta^-(v)} f_a =
\begin{cases}
F & (v = A) \\
-F & (v = F) \\
0 & (\text{その他})
\end{cases} \\
& 0 \le f_a \le u_a \quad (\forall a \in A)
\end{aligned}
$F$ が制約の右辺にも目的関数にも出てくるのが少し気持ち悪いかもしれませんが、$F$ を左辺に移項すれば普通のLPです。PuLPは自動でやってくれます。
PuLPで解いてみる
import pulp
prob = pulp.LpProblem('max_flow', pulp.LpMaximize)
# 各枝の流量。上限が容量
f = {a: pulp.LpVariable(f'f_{a[0]}{a[1]}', lowBound=0, upBound=CAP[a]) for a in ARCS}
F = pulp.LpVariable('F', lowBound=0) # 全体の流量も変数にする
prob += F # 目的関数：流量を最大化
for v in NODES:
b = F if v == SOURCE else (-F if v == SINK else 0)
prob += (pulp.lpSum(f[a] for a in out_arcs(v))
- pulp.lpSum(f[a] for a in in_arcs(v)) == b), f'flow_{v}'
prob.solve(pulp.PULP_CBC_CMD(msg=0))
print(f'状態={pulp.LpStatus[prob.status]} 最大流量={pulp.value(prob.objective)}')
print(f'{"枝":<10}{"流量":>6}{"容量":>6} 飽和')
for a in ARCS:
val = f[a].value()
print(f'{a[0]}->{a[1]:<8}{val:>6.0f}{CAP[a]:>6} '
f'{"★" if abs(val - CAP[a]) < 1e-9 else ""}')
状態=Optimal 最大流量=8.0
枝 流量 容量 飽和
A->B 3 5
A->C 5 5 ★
B->C 0 2
B->D 3 3 ★
C->D 2 2 ★
C->E 3 3 ★
D->F 5 6
E->D 0 1
E->F 3 4
最大流量は 8 でした。
結果を読む
図にするとこうなります。ラベルは「流量 / 容量」です。
（赤い枝と点線が何なのかは③で説明します。今は流量だけ見てください）
流れを経路に分解すると、こんな内訳になっています。
A→B→D→F : 3単位
A→C→D→F : 2単位
A→C→E→F : 3単位
合計 : 8単位
検算しましょう。
- A から出る量：A→B 3 + A→C 5 = 8 ✓
- F に入る量：D→F 5 + E→F 3 = 8 ✓
- D を見ると：入 B→D 3 + C→D 2 + E→D 0 = 5、出 D→F 5 ✓（保存則OK）
なぜ 8 で止まるのか
「A から出る容量は A→B 5 + A→C 5 = 10 あるのに、なぜ 8 しか流れないのか？」
飽和している枝（★）を見ると理由が見えてきます。
| 飽和している枝 | 容量 |
|---|---|
| A→C | 5 |
| B→D | 3 |
| C→D | 2 |
| C→E | 3 |
特に B→D、C→D、C→E の3本 に注目してください。この3本は「{A, B, C} から {D, E, F} へ渡る枝」を全部集めたものです。
{A, B, C} │ {D, E, F}
│
A → B ──────┼───→ D B→D 容量 3
│ │ ↑
↓ │ │
A → C ──────┼──────┘ C→D 容量 2
└────────┼───→ E C→E 容量 3
│
合計 8
A から F へ行くには、 必ずこの3本のどれかを通らなければなりません 。その合計容量が 3 + 2 + 3 = 8 なので、どうやっても 8 を超えられないわけです。
この「グラフを2つに切り分ける枝の集合」を カット（cut） と呼びます。そして 最大流量とカット容量の最小値は必ず一致します 。これが有名な 最大流最小カット定理 で、次回③のテーマです。
最大流は1通りとは限らない
ちなみに、最大流の解は一意ではありません。上の解では B→C に 0 が流れていますが、
A→B→C→D→F : 2単位
A→B→D→F : 3単位
A→C→E→F : 3単位
合計 : 8単位
でも 8 になります。 流量の値 8 は一意ですが、その内訳は複数あり得る ということですね。ソルバーによって違う答えが返ってくることもあります。
よくある拡張
始点・終点が複数ある場合
「工場が3か所、店舗が5か所」みたいなときは、 超始点（super source）と超終点（super sink） を追加します。
┌→ 工場1 ─┐ ┌→ 店舗1 ─┐
超始点 S ─────┼→ 工場2 ─┼→ ネットワーク ┼→ 店舗2 ─┼──→ 超終点 T
└→ 工場3 ─┘ └→ 店舗3 ─┘
容量 = 各工場の供給量 容量 = 各店舗の需要量
S から各工場への枝に「その工場の供給量」を容量として設定し、各店舗から T への枝に「その店舗の需要量」を設定すれば、あとは普通の1始点1終点の最大流として解けます。 問題を変形するのではなく、グラフを変形する という発想が便利です。
ノードにも容量がある場合
「この中継地点は1日100個までしか処理できない」のようにノードに容量があるときは、 ノードを2つに割ります 。
──→ v ──→ を ──→ v_in ──→ v_out ──→
容量 = ノードの容量
$v$ を $v_{in}$ と $v_{out}$ に分けて、その間に容量付きの枝を1本入れます。元の入枝は $v_{in}$ へ、出枝は $v_{out}$ から出るようにします。これでノード容量が枝容量に化けました。
こういう 「グラフを作り変えて既知の問題に帰着する」 テクニックはネットワーク最適化のあちこちで出てきます。
まとめ
- 最大流問題は「容量を超えない範囲で、始点から終点へ最大どれだけ流せるか」
- ①とほぼ同じ定式化 。違いは「容量制約を付ける」「湧き出し量 $F$ を変数にして最大化する」の2点だけ
- 今回の答えは 最大流量 8
- 8で止まる理由は {A,B,C} と {D,E,F} を分けるカットの容量が 8 だから
- 始点・終点が複数、ノードに容量、といった拡張は グラフを作り変えて帰着 できる
次回③は、今回チラッと出てきた 最小カット をちゃんと扱います。双対問題シリーズでやった弱双対定理・強双対定理が、ここで見事に効いてくるのでお楽しみに。
参考にした記事や本、論文等
- R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, "Network Flows: Theory, Algorithms, and Applications," Prentice Hall, 1993.
- L. R. Ford and D. R. Fulkerson, "Maximal flow through a network," Canadian Journal of Mathematics, vol. 8, pp. 399-404, 1956.