オペレーションズリサーチ 第 6 回¶
グラフ上の最適化：最短路問題と最大フロー問題¶
日本大学生産工学部 オペレーションズリサーチ（柿本・大前）
0. この資料の使い方¶
第 3・4 回で線形計画問題、第 5 回で整数計画問題を学びました。今回は、道路網や通信網のように「点と、点をつなぐ線」で表されるもの（グラフ）の上の最適化問題を扱います。取り上げるのは 最短路問題（出発ノードから到着ノードまでの最もコストの小さい経路）と 最大フロー問題（出発ノードから到着ノードへ最大でどれだけ流せるか）の 2 つです。
新しい解き方は出てきません。やることは「グラフを記号で書く → 定式化する → ソルバーで解く」で、これまでの回で学んだ記法（第 1 回）、線形計画問題（第 3・4 回）、0-1 変数とソルバー（第 5 回）をそのまま使います。
目的は次の 3 点です。
- グラフを記号（ノード $i \in V$、エッジ $(i, j) \in E$、コスト・容量の表）で読み、ノードから出るエッジ・入るエッジを表から拾える。
- 最短路問題を 0-1 変数で、最大フロー問題を実数の変数で 定式化 できる（フロー保存制約を $\sum$ で書き、展開できる）。
- 「定式化できればソルバーで解ける」ことと、「問題の構造を使った専用の方法の方が桁違いに速い」ことの両方を説明できる。
章立て¶
| 章 | 内容 |
|---|---|
| 1 | グラフの言葉（ノード、エッジ、無向と有向、表） |
| 2 | 最短路問題（0-1 変数、フロー保存制約。整数計画問題） |
| 3 | 最大フロー問題（流量の変数、容量制約。線形計画問題） |
| 4 | ソルバーで解く（PuLP） |
| 5 | まとめ：道具は問題の構造で選ぶ |
| 6 | 演習 |
| 付録 | 用語早見表 |
記法¶
ノードは $i, j \in V$、エッジはノードの組 $(i, j) \in E$ で表します。エッジ $(i, j)$ のコスト（長さ）を $c_{ij}$、容量を $u_{ij}$、決定変数を $x_{ij}$ と書きます。添字が 2 つの変数 $x_{ij}$ は、第 5 回の別冊『演習問題 1 の解説』§1 の $x_{ij}$（容器 $i$ に荷物 $j$ を入れる）と同じ書き方です。出発ノードを $s$、到着ノードを $t$ と書きます。
この資料のグラフは 無向グラフ（線に向きがなく、両方向に通れる）です。定式化のときだけ、各エッジを向きの違う 2 本に分けて考えます（§1.2）。
1. グラフの言葉¶
1.1 グラフとは¶
グラフ とは、いくつかの点と、点どうしをつなぐ線でできた図のことです。点を ノード、線を エッジ と呼びます。次の図がこの資料で使うグラフです（ノード 6 個、エッジ 8 本）。
グラフで表せるものはたくさんあります。道路網（交差点がノード、道路がエッジ）、通信網（ルータがノード、回線がエッジ）、鉄道網（駅がノード、線路がエッジ）などです。ノードの位置やエッジの曲がり方には意味がありません。「どのノードとどのノードがつながっているか」だけがグラフの情報です。
1.2 無向グラフと有向グラフ¶
上の図のように、エッジに向きがなく 両方向に通れる グラフを 無向グラフ と呼びます。ふつうの道路はどちらにも通れるので無向グラフです。一方、エッジに向きがあり 一方通行 のグラフを 有向グラフ と呼びます。有向グラフのエッジは矢印で描きます。
この資料では無向グラフで話を進めます。ただし、グラフ上の最適化問題の定式化では「ノード $i$ から出る」「ノード $i$ に入る」のように 向き を使います。そこで、無向のエッジ $\{i, j\}$ は 向きの違う 2 本のエッジ $(i, j)$ と $(j, i)$ で表す と約束します。$(i, j)$ は「$i$ から $j$ へ」、$(j, i)$ は「$j$ から $i$ へ」で（§1.4 の表では $(i, j)$ のマスと $(j, i)$ のマスに対応します）、コストや容量はどちらも同じ（$c_{ij} = c_{ji}$）です。両方向に通れる道を、向きの違う 2 本の一方通行の道と考えるわけです。こうすると、無向グラフも有向グラフも同じ式で扱えます。
1.3 記号¶
グラフは、ノードの集合 $V$ とエッジの集合 $E$ の組として $G = (V, E)$ と書きます。ノードには番号を付け、上の図では
$$ V = \{1, 2, 3, 4, 5, 6\} $$
です（第 1 回 §1.2）。$i \in V$ は「$i$ はノードの 1 つ」と読み、ノードの数は $\lvert V \rvert = 6$ です（第 1 回 §1.4、§1.5）。
無向グラフのエッジは、つなぐ 2 つのノードの組 $\{i, j\}$ で表します（向きがないので集合の記号で書きます。$\{2, 3\}$ と $\{3, 2\}$ は同じエッジです）。上の図のエッジの集合は
$$ E = \{\{1, 2\}, \{1, 3\}, \{2, 3\}, \{2, 4\}, \{3, 4\}, \{3, 5\}, \{4, 6\}, \{5, 6\}\} $$
で、$\lvert E \rvert = 8$ です。$\{2, 3\} \in E$ は「ノード 2 と 3 をつなぐエッジがある」、$\{1, 4\} \notin E$ は「ノード 1 と 4 をつなぐエッジはない」と読みます。
§1.2 の約束に従って、以降はエッジに向きを付けて扱います。向きを付けたエッジはノードの組 $(i, j)$ で表します。$(i, j)$ は「ノード $i$ からノード $j$ へのエッジ」です。無向のエッジ $\{i, j\}$ 1 本から $(i, j)$ と $(j, i)$ の 2 本ができます。以降、$E$ はこの向き付きのエッジの集合を指します。無向のエッジが 8 本なので、$E$ の要素は 16 個です。
$$ E = \{(1, 2), (1, 3), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (3, 5), (4, 2), (4, 3), (4, 6), (5, 3), (5, 6), (6, 4), (6, 5)\} $$
$(i, j) \in E$ は「ノード $i$ からノード $j$ へのエッジがある」と読みます。ノードの数は $\lvert V \rvert = 6$、エッジの数は $\lvert E \rvert = 16$ です（第 1 回 §1.5）。
エッジには数値が付きます。§2 では コスト $c_{ij}$（道の長さや所要時間。以降、エッジの長さをコストと呼びます）、§3 では 容量 $u_{ij}$（1 時間に流せる量）を使います。添字が 2 つ付くのは、エッジがノードの組で決まるからです（第 1 回 §2.4）。$c_{23} = 2$ は「エッジ $(2, 3)$ のコストが 2」と読みます。無向グラフなので $c_{23} = c_{32} = 2$ です。
出発ノードのノードを $s$、到着ノードのノードを $t$ と書きます。上の図では $s = 1$、$t = 6$ です。
1.4 表で与える¶
グラフの数値は、行がノード $i$、列がノード $j$ の表で与えます。次の表はコスト $c_{ij}$ です。
| $i \backslash j$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
|---|---|---|---|---|---|---|
| $1$ | 0 | 2 | 5 | 0 | 0 | 0 |
| $2$ | 2 | 0 | 2 | 6 | 0 | 0 |
| $3$ | 5 | 2 | 0 | 1 | 3 | 0 |
| $4$ | 0 | 6 | 1 | 0 | 0 | 2 |
| $5$ | 0 | 0 | 3 | 0 | 0 | 4 |
| $6$ | 0 | 0 | 0 | 2 | 4 | 0 |
マス $(i, j)$ の数が $c_{ij}$ です。$c_{34}$ は 3 行 4 列のマスなので $1$ です（ノード 3–4 のコスト）。「$0$」はエッジがないこと（$(i, j) \notin E$）を表します（隣接行列と同じ約束です。コストが $0$ のエッジがあるのではありません）。対角線のマスも $0$（自分から自分へのエッジはない）です。無向グラフなので、表は対角線について対称です（$(2, 3)$ のマスも $(3, 2)$ のマスも $2$）。
第 1 回 §2.3 の「添字と表の対応」そのものです。第 3 回の $a_{ij}$（原料 $i$、製品 $j$）と同じ見方で、行が 1 つ目の添字、列が 2 つ目の添字です。
この表は行列としても表現できます。特に、ノードの接続関係（エッジがあれば 1、なければ 0）を $\{0, 1\}^{n \times n}$ の行列で表したものを 隣接行列 と呼びます（$n$ はノードの数）。この授業では行列の計算はしないので、表のまま扱います。
1.5 出るエッジと入るエッジ¶
今回の定式化で何度も使うのが、「ノード $i$ から出るエッジ」と「ノード $i$ に入るエッジ」です。§1.2 の約束で各エッジに向きを付けたので、無向グラフでも次のように決まります。
- ノード $i$ から 出る エッジ $(i, j)$ は、表の $i$ 行 で $0$ でないマス。
- ノード $i$ に 入る エッジ $(j, i)$ は、表の $i$ 列 で $0$ でないマス。
ノード 3 なら、3 行を見ると $(3, 1)$、$(3, 2)$、$(3, 4)$、$(3, 5)$ が出るエッジ、3 列を見ると $(1, 3)$、$(2, 3)$、$(4, 3)$、$(5, 3)$ が入るエッジです。無向グラフでは、出るエッジと入るエッジの相手（隣のノード 1、2、4、5）は同じで、向きだけが違います。表が対称なので、$i$ 行と $i$ 列には同じ数が並びます。§2 の定式化で使うのは、この「出るエッジ」「入るエッジ」の区別だけです（コストを行や列で足すことはしません）。
すべてのエッジについての和は $\sum_{(i, j) \in E}$ と書きます。表の $0$ でないマス全部（16 個）を足すことです。
$\sum_{j : (k, j) \in E}$ の範囲は「$(k, j)$ がエッジであるような $j$」で、すべての $j \in V$ ではありません。ただし、表ではエッジのないマスを $0$ にしてあるので、すべての $j \in V$ について $c_{kj}$ を足しても $0$ のマスは値を変えず、同じ $11$ になります。どちらで読んでも値は同じです。§2 以降は変数がエッジにしかない（$16$ 個）ので、$\sum$ の範囲はエッジで書きます。
2. 最短路問題¶
2.1 問題¶
§1 のグラフを道路網とします。エッジの数字は道のコスト（所要時間や距離）です。ノード 1 からノード 6 まで、道を通って行くとき、通る道のコストの合計が最小になる経路を求めてください。
これを 最短路問題 と呼びます。カーナビや乗換案内が解いている問題です。
ここで 経路 とは、$s$ から始まり $t$ で終わるノードの列 $v_0 \to v_1 \to \cdots \to v_m$（$v_0 = s$、$v_m = t$）で、隣り合う $v_{k-1}$ と $v_k$ の間にエッジがあるものです。同じノードを 2 度通る経路は遠回りなので、この資料では同じノードを 2 度通らない経路だけを考えます。始点と終点が同じノードになる経路を 閉路 と呼びます（§2.7 で使います）。
このグラフは小さいので、ノード 1 からノード 6 への経路を全部書き出せます（7 本あります）。
| 経路 | コスト | |
|---|---|---|
| $1 \to 2 \to 3 \to 4 \to 6$ | $2 + 2 + 1 + 2 = 7$ | ← 最短 |
| $1 \to 3 \to 4 \to 6$ | $5 + 1 + 2 = 8$ | |
| $1 \to 2 \to 4 \to 6$ | $2 + 6 + 2 = 10$ | |
| $1 \to 2 \to 3 \to 5 \to 6$ | $2 + 2 + 3 + 4 = 11$ | |
| $1 \to 3 \to 5 \to 6$ | $5 + 3 + 4 = 12$ | |
| $1 \to 3 \to 2 \to 4 \to 6$ | $5 + 2 + 6 + 2 = 15$ | |
| $1 \to 2 \to 4 \to 3 \to 5 \to 6$ | $2 + 6 + 1 + 3 + 4 = 16$ |
最短路は $1 \to 2 \to 3 \to 4 \to 6$ で、コストは $7$ です。通るエッジの数が最も少ない経路（3 本）が最短とは限らないことに注意してください。
経路を全部書き出すやり方は、ノードが増えると使えません。経路の数は爆発的に増えます（第 5 回 §3 の全列挙と同じ事情です）。そこで、第 3 回・第 5 回と同じように 定式化 して、ソルバーに解かせます。
2.2 決定変数¶
決めることは「エッジ $(i, j)$ を通るか、通らないか」です。「する・しない」なので 0-1 変数です（第 5 回 §2.2）。
$$ x_{ij} = \begin{cases} 1 & \text{エッジ } (i, j) \text{ を通る} \\ 0 & \text{通らない} \end{cases}, \quad (i, j) \in E $$
§1.2 の約束で、無向のエッジ 1 本に $(i, j)$ と $(j, i)$ の 2 本があるので、変数は向きごとに 1 つ、合計 $\lvert E \rvert = 16$ 個です。
$$ x_{12}, \ x_{13}, \ x_{21}, \ x_{23}, \ x_{24}, \ x_{31}, \ x_{32}, \ x_{34}, \ x_{35}, \ x_{42}, \ x_{43}, \ x_{46}, \ x_{53}, \ x_{56}, \ x_{64}, \ x_{65} $$
$x_{23}$ は「ノード 2 からノード 3 へ進む」、$x_{32}$ は「ノード 3 からノード 2 へ進む」です。
次の図のように、矢印 1 本に変数が 1 つ付きます。
経路 $1 \to 2 \to 3 \to 4 \to 6$ は、$x_{12}, x_{23}, x_{34}, x_{46}$ が $1$ で、他の 12 個（逆向きの $x_{21}$、$x_{32}$ なども）は $0$ です。
2.3 目的関数¶
通った道のコストの合計を最小にします。通らない道は $x_{ij} = 0$ で消えるので（第 5 回 §2.2）、すべてのエッジについて「コスト × 変数」を足せば、通った道のコストの合計になります。
$$ z = \sum_{(i, j) \in E} c_{ij} x_{ij} \rightarrow \min $$
展開すると（表の $0$ でないマスを、1 行目から順に左から右へ拾います。16 項あります）
$$ \begin{aligned} z = {} & 2x_{12} + 5x_{13} + 2x_{21} + 2x_{23} + 6x_{24} + 5x_{31} + 2x_{32} + x_{34} \\ & \quad + 3x_{35} + 6x_{42} + x_{43} + 2x_{46} + 3x_{53} + 4x_{56} + 2x_{64} + 4x_{65} \rightarrow \min \end{aligned} $$
です。第 5 回のナップサック問題の $\sum_{j \in J} c_j x_j$ と同じ形で、添字が品物 $j$ からエッジ $(i, j)$ に変わっただけです。
経路 $1 \to 2 \to 3 \to 4 \to 6$ では、次の図のように通った矢印だけが $x_{ij} = 1$ で、$0$ の項は消えるので $z = 2 + 2 + 1 + 2 = 7$ です。
2.4 制約条件：フロー保存¶
目的関数を最小にするだけなら、すべて $x_{ij} = 0$（どの道も通らない）が最小です。「ノード 1 からノード 6 への経路になっている」ことを制約で表さなければなりません。
次のように考えます。出発ノード $s$ に荷物が 1 個あり、それを到着ノード $t$ まで運びます。荷物はエッジに沿って運ばれ、途中のノードに置き去りにはしません。このとき、各ノードで「出るエッジで運ぶ個数 − 入るエッジで運ぶ個数」を数えると
- 出発ノード $s$（ノード 1）は、荷物が出ていくだけなので $1$、
- 到着ノード $t$（ノード 6）は、荷物が入ってくるだけなので $-1$、
- 途中のノードは、通るなら「入って出る」（$1 - 1 = 0$）、通らないなら「入らず出ず」（$0 - 0 = 0$）なので $0$
です。これを フロー保存制約 と呼びます（フローは「流れ」のことです）。「流出エッジ数 − 流入エッジ数」が $1$、$-1$、$0$ のどれかになる、という制約です。式で書くと
$$ \sum_{j : (k, j) \in E} x_{kj} - \sum_{i : (i, k) \in E} x_{ik} = b_k, \quad \forall k \in V, \qquad b_k = \begin{cases} 1 & k = s \\ -1 & k = t \\ 0 & k \in V \setminus \{s, t\} \end{cases} $$
です。左辺の 1 つ目の $\sum_{j : (k, j) \in E} x_{kj}$ は、$k$ 行の $0$ でないマス（§1.5 の出るエッジ）の変数を足したもので、「$(k, j)$ がエッジであるような $j$ だけについて足す」と読みます。$x_{kj}$ は $0$ か $1$ なので、この和は「通って出るエッジの本数」（流出エッジ数）です。2 つ目の $\sum_{i : (i, k) \in E} x_{ik}$ は $k$ 列の変数の和で、「通って入るエッジの本数」（流入エッジ数）です（第 1 回 §2.5 の、添字を 1 つ固定してもう 1 つで足す形。第 5 回の別冊 §1 の行の和・列の和と同じです）。表の $0$ のマスには変数がないので項はありませんが、$0$ の項があると考えて足しても値は同じです。つまり保存制約は「通って出る本数 − 通って入る本数 $= b_k$」です。$\forall k \in V$ なので、ノードの数だけ（6 本）式があります（第 1 回 §4.2）。
展開してみます。表の $k$ 行と $k$ 列を見て、$0$ でないマスだけ拾います。無向グラフでは、隣のノードごとに出る $x_{kj}$ と入る $x_{ik}$ が対になります。
手順 1 ノード $k = 1$（出発ノード、$b_1 = 1$）。1 行の $0$ でないマスは $(1, 2)$、$(1, 3)$（出る $x_{12}$、$x_{13}$）、1 列の $0$ でないマスは $(2, 1)$、$(3, 1)$（入る $x_{21}$、$x_{31}$）です。
$$ x_{12} + x_{13} - x_{21} - x_{31} = 1 $$
手順 2 ノード $k = 3$（途中、$b_3 = 0$）。3 行から出るエッジ $(3, 1)$、$(3, 2)$、$(3, 4)$、$(3, 5)$、3 列から入るエッジ $(1, 3)$、$(2, 3)$、$(4, 3)$、$(5, 3)$ を拾います。
$$ x_{31} + x_{32} + x_{34} + x_{35} - x_{13} - x_{23} - x_{43} - x_{53} = 0 $$
手順 3 ノード $k = 6$（到着ノード、$b_6 = -1$）。6 行から $(6, 4)$、$(6, 5)$、6 列から $(4, 6)$、$(5, 6)$ を拾います。
$$ x_{64} + x_{65} - x_{46} - x_{56} = -1 $$
3 つのノードを図で見ると次のとおりです。注目するノードから出る矢印（赤）の変数を足し、入る矢印（青）の変数を引いています。
残りのノード 2、4、5 も同じです。6 本をまとめると次のとおりです。
$$ \begin{aligned} & x_{12} + x_{13} - x_{21} - x_{31} = 1 && (k = 1) \\ & x_{21} + x_{23} + x_{24} - x_{12} - x_{32} - x_{42} = 0 && (k = 2) \\ & x_{31} + x_{32} + x_{34} + x_{35} - x_{13} - x_{23} - x_{43} - x_{53} = 0 && (k = 3) \\ & x_{42} + x_{43} + x_{46} - x_{24} - x_{34} - x_{64} = 0 && (k = 4) \\ & x_{53} + x_{56} - x_{35} - x_{65} = 0 && (k = 5) \\ & x_{64} + x_{65} - x_{46} - x_{56} = -1 && (k = 6) \end{aligned} $$
経路 $1 \to 2 \to 3 \to 4 \to 6$（$x_{12}, x_{23}, x_{34}, x_{46}$ が $1$、他は $0$）がこの 6 本を満たすことを確かめてください。例えばノード 2 の式は、出る $x_{23} = 1$ と入る $x_{12} = 1$ だけが残り、$1 - 1 = 0$ です。
入るエッジの変数は、$k$ 列の $x_{ik}$（2 つ目の添字が $k$）です。出るエッジの変数は $k$ 行の $x_{kj}$（1 つ目の添字が $k$）で、無向グラフでは両方が式に現れます。ノード 3 に入るエッジの変数は $x_{13}$、$x_{23}$、$x_{43}$、$x_{53}$ で、表では 3 列を見ます。
2.5 定式化¶
まとめると、最短路問題の定式化は次のとおりです。
$$ \begin{aligned} & z = \sum_{(i, j) \in E} c_{ij} x_{ij} \rightarrow \min, \\ \text{s.t.} \quad & \sum_{j : (k, j) \in E} x_{kj} - \sum_{i : (i, k) \in E} x_{ik} = b_k, \quad \forall k \in V, \\ & x_{ij} \in \{0, 1\}, \quad \forall (i, j) \in E. \end{aligned} $$
ここで $b_s = 1$、$b_t = -1$、$b_k = 0$（$k \in V \setminus \{s, t\}$）です。$k$ は注目するノード、$i, j$ は表の行と列の添字です。§1 のグラフで展開すると
$$ \begin{aligned} & z = 2x_{12} + 5x_{13} + 2x_{21} + 2x_{23} + 6x_{24} + 5x_{31} + 2x_{32} + x_{34} \\ & \quad + 3x_{35} + 6x_{42} + x_{43} + 2x_{46} + 3x_{53} + 4x_{56} + 2x_{64} + 4x_{65} \rightarrow \min, \\ \text{s.t.} \quad & x_{12} + x_{13} - x_{21} - x_{31} = 1, \\ & x_{21} + x_{23} + x_{24} - x_{12} - x_{32} - x_{42} = 0, \\ & x_{31} + x_{32} + x_{34} + x_{35} - x_{13} - x_{23} - x_{43} - x_{53} = 0, \\ & x_{42} + x_{43} + x_{46} - x_{24} - x_{34} - x_{64} = 0, \\ & x_{53} + x_{56} - x_{35} - x_{65} = 0, \\ & x_{64} + x_{65} - x_{46} - x_{56} = -1, \\ & x_{ij} \in \{0, 1\}, \quad \forall (i, j) \in E. \end{aligned} $$
となります。変数が $\lvert E \rvert = 16$ 個、フロー保存制約が $\lvert V \rvert = 6$ 本です。グラフが大きくなっても式の形は変わらず、表から拾うだけで展開できます。有向グラフ（一方通行の道がある）なら、表の対称でないマスをそのまま拾うだけで、式の形は同じです。
決定変数が 0-1 変数なので、これは 整数計画問題 です（第 5 回 §1.1）。第 5 回で学んだとおり、ソルバーは分枝限定法で解きます。
2.6 答え¶
ソルバー（§4.2）で解くと、最適解は $x^*_{12}, x^*_{23}, x^*_{34}, x^*_{46}$ が $1$、他は $0$、最適値は $z^* = 7$ です。§2.1 で全部書き出して見つけた最短路と一致します。
2.7 注意：フロー保存制約だけで経路になるのか¶
フロー保存制約を満たす 0-1 の解は、「$s$ から $t$ への経路 1 本」のほかに、それと「ぐるりと一周する閉路」を組み合わせたものも含みます。無向グラフでは、同じエッジを往復する $x_{ij} = x_{ji} = 1$ も小さな閉路です。しかしコストがすべて正なら、閉路を含むと目的関数が増えるので、最適解に閉路は含まれません。したがって最適解は必ず 1 本の経路で、同じエッジの往復も起こりません。コストが負のエッジがある場合は話が変わりますが、この授業では扱いません。
もう 1 つ、知っておくとよいことがあります。この問題は、$x_{ij} \in \{0, 1\}$ を $0 \le x_{ij} \le 1$ にゆるめた LP 緩和（第 5 回 §5.1）を解いても、最適解がちょうど 0 か 1 になることが知られています（理由はこの授業の範囲外です）。つまり分枝限定法の分枝は起こらず、線形計画問題として解けてしまいます。これはフロー保存制約という形の持つ性質で、§5.2 の「問題の構造」の一例です。
3. 最大フロー問題¶
3.1 問題¶
§1 と同じグラフを水道管の網とします。ただし今度は、エッジの数字は道のコストではなく 容量（1 時間にそのエッジに流せる量の上限）です。ノード 1 からノード 6 へ、1 時間に最大でどれだけ流せるでしょうか。水はどちらの向きにも流せますが、途中のノードに水をためることはできません（入った量と出る量が等しい）。
これを 最大フロー問題 と呼びます。通信網の帯域、物流の輸送量などがこの形になります。容量 $u_{ij}$ の表は次のとおりです（グラフの形は §1 と同じで、数値だけ違います。無向グラフなので対称です）。
| $i \backslash j$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
|---|---|---|---|---|---|---|
| $1$ | 0 | 6 | 3 | 0 | 0 | 0 |
| $2$ | 6 | 0 | 2 | 3 | 0 | 0 |
| $3$ | 3 | 2 | 0 | 2 | 3 | 0 |
| $4$ | 0 | 3 | 2 | 0 | 0 | 6 |
| $5$ | 0 | 0 | 3 | 0 | 0 | 6 |
| $6$ | 0 | 0 | 0 | 6 | 6 | 0 |
まず目視で考えてみます。経路ごとに流すと、$1 \to 2 \to 4 \to 6$ に $3$（エッジ $\{2, 4\}$ の容量）、$1 \to 3 \to 5 \to 6$ に $3$、$1 \to 2 \to 3 \to 4 \to 6$ に $2$ で、合計 $8$ 流せます。これ以上流せないことは、次のように確かめられます。ノード $\{1, 2, 3\}$ と残りのノード $\{4, 5, 6\}$ をまたぐエッジは $\{2, 4\}$、$\{3, 4\}$、$\{3, 5\}$ の 3 本で、容量の和は $3 + 2 + 3 = 8$ です。ノード 6 へ行く水は必ずこの 3 本のどれかを通るので、$8$ より多くは流せません。
「グラフをノードの集まりで 2 つに分け、境目をまたぐエッジの容量を足す」と、流せる量の上限が分かります。目視で最大フローを求めるときは、この方法で「これ以上は無理」を確かめます（最大フローの値は、分け方をいろいろ変えたときの上限の最小値に等しいことが知られています）。
3.2 決定変数¶
決めることは「各エッジに、どちらの向きにどれだけ流すか」です。§1.2 の約束どおり、向きごとに変数を用意します。
$$ x_{ij} = \text{エッジ } (i, j) \text{ に（} i \text{ から } j \text{ へ）流す量}, \quad (i, j) \in E $$
§2 と同じ記号 $x_{ij}$ ですが、意味が違います。§2 の $x_{ij}$ は「通るか通らないか」の 0-1 変数でした。ここでの $x_{ij}$ は 量 で、$0$ 以上 $u_{ij}$ 以下の実数（小数も可）です。記号で書くと $x_{ij} \in \mathbb{R}$、$0 \le x_{ij} \le u_{ij}$ で、§2 の $x_{ij} \in \{0, 1\}$ とは違います。変数の数はエッジの数と同じ $16$ 個です。同じエッジの両方向に同時に流すのは無駄なので（打ち消し合うだけです）、最適解では $x_{ij}$ と $x_{ji}$ のどちらかが $0$ になります。
3.3 制約条件¶
容量制約 各エッジには容量までしか流せません。
$$ 0 \le x_{ij} \le u_{ij}, \quad \forall (i, j) \in E $$
展開すると $16$ 本です（無向グラフなので、$0 \le x_{12} \le 6$ と $0 \le x_{21} \le 6$ のように、同じ容量が両方向に付きます）。
$$ 0 \le x_{12} \le 6, \ 0 \le x_{13} \le 3, \ 0 \le x_{21} \le 6, \ 0 \le x_{23} \le 2, \ 0 \le x_{24} \le 3, \ 0 \le x_{31} \le 3, \ 0 \le x_{32} \le 2, \ 0 \le x_{34} \le 2, \ 0 \le x_{35} \le 3, \ 0 \le x_{42} \le 3, \ 0 \le x_{43} \le 2, \ 0 \le x_{46} \le 6, \ 0 \le x_{53} \le 3, \ 0 \le x_{56} \le 6, \ 0 \le x_{64} \le 6, \ 0 \le x_{65} \le 6 $$
フロー保存制約 途中のノードでは、入った量と出る量が等しくなければなりません。§3.1 の流し方でノード $3$ を見ると、入る量は $3$ 列の和 $x_{13} + x_{23} + x_{43} + x_{53} = 3 + 2 + 0 + 0 = 5$、出る量は $3$ 行の和 $x_{31} + x_{32} + x_{34} + x_{35} = 0 + 0 + 2 + 3 = 5$ で、確かに等しくなっています（§1.5 の和の読み方そのものです。出る $x_{3j}$ と入る $x_{i3}$ は別の変数で、コストのような対称性はありません）。
これを §2.4 と同じ「出る − 入る」の式で書きます。途中のノードでは右辺が $0$ です。出発ノード $s$ では、「出る − 入る」が流した量そのものです。この量を $f$ と書きます（$f$ も変数です）。到着ノード $t$ には流れが全部入ってくるので、「出る − 入る」は $-f$ です。
$$ \begin{aligned} & \sum_{j : (s, j) \in E} x_{sj} - \sum_{i : (i, s) \in E} x_{is} = f && \text{（出発ノード）} \\ & \sum_{j : (t, j) \in E} x_{tj} - \sum_{i : (i, t) \in E} x_{it} = -f && \text{（到着ノード）} \\ & \sum_{j : (k, j) \in E} x_{kj} - \sum_{i : (i, k) \in E} x_{ik} = 0, \quad \forall k \in V \setminus \{s, t\} && \text{（途中のノード）} \end{aligned} $$
$V \setminus \{s, t\}$ は「$V$ から $s$ と $t$ を除いた集合」、つまり途中のノード $\{2, 3, 4, 5\}$ です。§2.4 の右辺 $1$、$-1$、$0$ の $1$ が $f$ に変わっただけです。展開すると $6$ 本です。
$$ \begin{aligned} & x_{12} + x_{13} - x_{21} - x_{31} = f && (k = 1 = s) \\ & x_{21} + x_{23} + x_{24} - x_{12} - x_{32} - x_{42} = 0 && (k = 2) \\ & x_{31} + x_{32} + x_{34} + x_{35} - x_{13} - x_{23} - x_{43} - x_{53} = 0 && (k = 3) \\ & x_{42} + x_{43} + x_{46} - x_{24} - x_{34} - x_{64} = 0 && (k = 4) \\ & x_{53} + x_{56} - x_{35} - x_{65} = 0 && (k = 5) \\ & x_{64} + x_{65} - x_{46} - x_{56} = -f && (k = 6 = t) \end{aligned} $$
§2.4 の展開と比べてください。左辺は同じで、右辺の $1$ が $f$ になっています。なお、$6$ 本の式の左辺を全部足すと $0$ になります（各変数 $x_{ij}$ は、ノード $i$ の「出る」に $+1$ 回、ノード $j$ の「入る」に $-1$ 回現れて消えます）。したがって到着ノードの式（$k = 6$）は他の $5$ 本から自動的に成り立ち、省いても同じ問題です。本によっては省いた形で書いてあります。
3.4 目的関数¶
流した量 $f$ を最大にします。
$$ f \rightarrow \max $$
$f$ は §3.3 の出発ノードの式により、出発ノードの「出る − 入る」$x_{12} + x_{13} - x_{21} - x_{31}$ に等しい量です。無向グラフでは出発ノードに戻ってくる向きの変数（$x_{21}$、$x_{31}$）もあるので、「出る」だけでなく「出る − 入る」で数えます（出発ノードに戻す流れは数えません）。
3.5 定式化¶
$$ \begin{aligned} & f \rightarrow \max, \\ \text{s.t.} \quad & \sum_{j : (s, j) \in E} x_{sj} - \sum_{i : (i, s) \in E} x_{is} = f, \\ & \sum_{j : (t, j) \in E} x_{tj} - \sum_{i : (i, t) \in E} x_{it} = -f, \\ & \sum_{j : (k, j) \in E} x_{kj} - \sum_{i : (i, k) \in E} x_{ik} = 0, \quad \forall k \in V \setminus \{s, t\}, \\ & 0 \le x_{ij} \le u_{ij}, \quad \forall (i, j) \in E. \end{aligned} $$
変数は $x_{ij}$（$16$ 個）と $f$ です。式の 3 つの部品（出発ノードの 出る − 入る $= f$ と到着ノードの 出る − 入る $= -f$、途中のノードの 入る = 出る、各エッジの容量）をグラフの上に示すと次のとおりです。
§1 のグラフで展開すると
$$ \begin{aligned} & f \rightarrow \max, \\ \text{s.t.} \quad & x_{12} + x_{13} - x_{21} - x_{31} = f, \\ & x_{21} + x_{23} + x_{24} - x_{12} - x_{32} - x_{42} = 0, \\ & x_{31} + x_{32} + x_{34} + x_{35} - x_{13} - x_{23} - x_{43} - x_{53} = 0, \\ & x_{42} + x_{43} + x_{46} - x_{24} - x_{34} - x_{64} = 0, \\ & x_{53} + x_{56} - x_{35} - x_{65} = 0, \\ & x_{64} + x_{65} - x_{46} - x_{56} = -f, \\ & 0 \le x_{ij} \le u_{ij}, \quad \forall (i, j) \in E \ (16 \text{ 本}). \end{aligned} $$
です。目的関数も制約条件もすべて 1 次式で、変数は実数です。つまり 線形計画問題（第 3 回 §3.1）で、単体法（第 4 回）で解けます。変数が $17$ 個あるので図解法は使えませんが、ソルバーなら一瞬です。
3.6 答え¶
ソルバー（§4.3）で解くと、最適値は $f^* = 8$ で、各エッジの流れは次のとおりです（流れない向きの変数は $0$ です）。
| エッジ $\{i, j\}$ | $\{1, 2\}$ | $\{1, 3\}$ | $\{2, 3\}$ | $\{2, 4\}$ | $\{3, 4\}$ | $\{3, 5\}$ | $\{4, 6\}$ | $\{5, 6\}$ |
|---|---|---|---|---|---|---|---|---|
| 容量 $u_{ij}$ | $6$ | $3$ | $2$ | $3$ | $2$ | $3$ | $6$ | $6$ |
| 流れる向き | $1 \to 2$ | $1 \to 3$ | $2 \to 3$ | $2 \to 4$ | $3 \to 4$ | $3 \to 5$ | $4 \to 6$ | $5 \to 6$ |
| 流量 $x^*$ | $5$ | $3$ | $2$ | $3$ | $2$ | $3$ | $5$ | $3$ |
§3.1 の目視の答えと一致します。容量いっぱいまで流しているエッジ（図の赤）が $\{1, 3\}$、$\{2, 3\}$、$\{2, 4\}$、$\{3, 4\}$、$\{3, 5\}$ で、ノード $\{1, 2, 3\}$ と $\{4, 5, 6\}$ をまたぐ 3 本がすべて容量いっぱいです。ここが「ボトルネック」です。フロー保存も確かめてください。ノード 2 には $x_{12} = 5$ が入り、$x_{23} = 2$ と $x_{24} = 3$ が出ています。
3.7 最短路問題と最大フロー問題の比較¶
| 最短路問題（§2） | 最大フロー問題（§3） | |
|---|---|---|
| 決定変数 $x_{ij}$ の意味 | エッジ $(i, j)$ を通るか（$1$ か $0$） | エッジ $(i, j)$ に $i$ から $j$ へ流す量 |
| 変数の型 | $x_{ij} \in \{0, 1\}$ | $0 \le x_{ij} \le u_{ij}$（実数） |
| 目的関数 | $\sum_{(i, j) \in E} c_{ij} x_{ij} \rightarrow \min$ | $f \rightarrow \max$（$f$ は出発ノードの「出る − 入る」） |
| フロー保存制約の右辺 | $s$ で $1$、$t$ で $-1$、途中で $0$ | $s$ で $f$、$t$ で $-f$、途中で $0$ |
| エッジの数値 | コスト $c_{ij}$ | 容量 $u_{ij}$ |
| 問題の種類 | 整数計画問題 | 線形計画問題 |
共通しているのは フロー保存制約「出る − 入る $=$ 右辺」です。グラフ上の最適化問題の多くがこの形の制約を持ちます。例えば、各エッジに費用と容量があって、決まった量を最も安く流す 最小費用流問題 は、§2 の目的関数と §3 の容量制約を組み合わせたものです（この授業では扱いません）。
4. ソルバーで解く（PuLP）¶
4.1 グラフのデータの持ち方¶
第 5 回 §7 と同じく PuLP（と CBC）を使います。この節のコードは配布するノートブック 06_pulp.ipynb に入っています（Google Colab で実行。提出は不要です。Colab では最初に !pip install pulp cbcbox が必要です）。
グラフは、エッジ $(i, j)$ をキーにした 辞書 で持ちます。無向のエッジは 8 本なので、まず 8 本分を書き、§1.2 の約束どおり逆向きを足して 16 本にします。
edges = {(1, 2): 2, (1, 3): 5, (2, 3): 2, (2, 4): 6, (3, 4): 1, (3, 5): 3, (4, 6): 2, (5, 6): 4} # 無向のエッジ {i, j} とコスト
c = {}
for (i, j), v in edges.items():
c[i, j] = v # (i, j)
c[j, i] = v # (j, i) も同じコスト
E = list(c) # エッジの集合 E（16 本）
V = [1, 2, 3, 4, 5, 6] # ノードの集合 V
「ノード $k$ から出るエッジ」は [(i, j) for (i, j) in E if i == k]、「入るエッジ」は [(i, j) for (i, j) in E if j == k] です。表の $k$ 行、$k$ 列を拾うのと同じです。有向グラフ（一方通行）なら、逆向きを足す 2 行を書かなければよいだけです。
4.2 最短路問題¶
§2.5 の定式化をそのまま書きます。変数は (i, j) をキーにした辞書です（第 5 回の別冊 §3 の $x_{ij}$ と同じ）。
import pulp
edges = {(1, 2): 2, (1, 3): 5, (2, 3): 2, (2, 4): 6, (3, 4): 1, (3, 5): 3, (4, 6): 2, (5, 6): 4} # 無向のエッジとコスト c_ij
c = {}
for (i, j), v in edges.items(): # 無向のエッジを向きの違う 2 本にする
c[i, j] = v
c[j, i] = v
E = list(c) # エッジの集合（16 本）
V = [1, 2, 3, 4, 5, 6] # ノードの集合
s, t = 1, 6 # 出発ノード、到着ノード
b = {i: (1 if i == s else -1 if i == t else 0) for i in V} # フロー保存制約の右辺 b_i
prob = pulp.LpProblem("shortest_path", pulp.LpMinimize)
x = {(i, j): prob.add_variable(f"x{i}{j}", cat="Binary") for (i, j) in E} # x_ij ∈ {0, 1}
prob += pulp.lpSum(c[i, j] * x[i, j] for (i, j) in E) # z = Σ c_ij x_ij → min
for k in V: # ∀k ∈ V
prob += (pulp.lpSum(x[i, j] for (i, j) in E if i == k) # 出るエッジの和（k 行）
- pulp.lpSum(x[i, j] for (i, j) in E if j == k) == b[k]) # − 入るエッジの和（k 列）= b_k
stats = prob.solve(pulp.COIN_CMD(msg=0))
print("状態:", stats.status_str)
print("最適値（コスト）:", pulp.value(prob.objective))
path = [(i, j) for (i, j) in E if x[i, j].value() > 0.5]
print("通るエッジ:", path)
状態: Optimal 最適値（コスト）: 7.0 通るエッジ: [(1, 2), (2, 3), (3, 4), (4, 6)]
§2.6 のとおり、コスト $7$ で、通るエッジは $(1, 2)$、$(2, 3)$、$(3, 4)$、$(4, 6)$ です。for k in V: の中の 1 行が、フロー保存制約の $\forall k \in V$ に対応します。if i == k が「出るエッジ」（$k$ 行）、if j == k が「入るエッジ」（$k$ 列）の条件です。
4.3 最大フロー問題¶
§3.5 の定式化です。変数は実数で、lowBound=0, upBound=u[i, j] が容量制約 $0 \le x_{ij} \le u_{ij}$ です。流す量 $f$ も変数にして（prob.add_variable("f", lowBound=0)）、目的関数は f、フロー保存制約の右辺は $s$ で f、$t$ で -f、途中で 0 です。結果は無向のエッジごとに、流れる向きと量（$x_{ij} - x_{ji}$ の符号と大きさ）で表示します。
import pulp
edges = {(1, 2): 6, (1, 3): 3, (2, 3): 2, (2, 4): 3, (3, 4): 2, (3, 5): 3, (4, 6): 6, (5, 6): 6} # 無向のエッジと容量 u_ij
u = {}
for (i, j), v in edges.items():
u[i, j] = v
u[j, i] = v
E = list(u)
V = [1, 2, 3, 4, 5, 6]
s, t = 1, 6
prob = pulp.LpProblem("max_flow", pulp.LpMaximize)
x = {(i, j): prob.add_variable(f"x{i}{j}", lowBound=0, upBound=u[i, j]) for (i, j) in E} # 0 ≤ x_ij ≤ u_ij（実数）
f = prob.add_variable("f", lowBound=0) # 流す量 f
prob += f # f → max
for k in V: # ∀k ∈ V
rhs = f if k == s else -f if k == t else 0 # 右辺: s は f、t は −f、途中は 0
prob += (pulp.lpSum(x[i, j] for (i, j) in E if i == k)
- pulp.lpSum(x[i, j] for (i, j) in E if j == k) == rhs) # 出る − 入る = 右辺
stats = prob.solve(pulp.COIN_CMD(msg=0))
print("状態:", stats.status_str)
print("最適値（流せる量）:", f"{pulp.value(prob.objective):g}")
for (i, j) in edges: # 無向のエッジごとに、流れる向きと量
v = x[i, j].value() - x[j, i].value()
a, b_ = (i, j) if v >= 0 else (j, i)
print(f" エッジ {{{i}, {j}}}: {a} → {b_} に {abs(v):g} / {u[i, j]}")
状態: Optimal
最適値（流せる量）: 8
エッジ {1, 2}: 1 → 2 に 5 / 6
エッジ {1, 3}: 1 → 3 に 3 / 3
エッジ {2, 3}: 2 → 3 に 2 / 2
エッジ {2, 4}: 2 → 4 に 3 / 3
エッジ {3, 4}: 3 → 4 に 2 / 2
エッジ {3, 5}: 3 → 5 に 3 / 3
エッジ {4, 6}: 4 → 6 に 5 / 6
エッジ {5, 6}: 5 → 6 に 3 / 6
§3.6 のとおり、最大フローの値は $8$ です。
4.4 定式化とプログラムの対応¶
| 定式化 | PuLP |
|---|---|
| 無向のエッジ $\{i, j\}$ を 2 本に | c[i, j] = v と c[j, i] = v |
| エッジのコスト $c_{ij}$、容量 $u_{ij}$ | 辞書 c[i, j]、u[i, j]（キーはエッジ (i, j)） |
| $x_{ij} \in \{0, 1\}$ | prob.add_variable(名前, cat="Binary") |
| $0 \le x_{ij} \le u_{ij}$ | prob.add_variable(名前, lowBound=0, upBound=u[i, j]) |
| $\sum_{(i, j) \in E} c_{ij} x_{ij}$ | pulp.lpSum(c[i, j] * x[i, j] for (i, j) in E) |
| $\sum_{j : (k, j) \in E} x_{kj}$（出るエッジ、$k$ 行） | pulp.lpSum(x[i, j] for (i, j) in E if i == k) |
| $\sum_{i : (i, k) \in E} x_{ik}$（入るエッジ、$k$ 列） | pulp.lpSum(x[i, j] for (i, j) in E if j == k) |
| $\forall k \in V$ | for k in V: の中で prob += … |
| 右辺の $f$、$-f$、$0$ | rhs = f if k == s else -f if k == t else 0 |
| 解く | stats = prob.solve(pulp.COIN_CMD(msg=0)) |
第 5 回 §7.4 の表に、「エッジをキーにした辞書」と「出る・入るの条件付きの和」が加わっただけです。グラフのデータ（辞書）を差し替えれば、どんなグラフでも同じプログラムで解けます。
5. まとめ：道具は問題の構造で選ぶ¶
5.1 グラフ上の最適化問題は他にもある：施設配置¶
最短路と最大フローのほかにも、グラフの上で定式化できる問題はたくさんあります。1 つだけ紹介します。道路網の上に、ガソリンスタンドや充電スタンドのような施設を $p$ 個置く問題です。
道路網の上に、いくつかの「流れ」（出発ノードから到着ノードへ向かう交通）があり、流れ $j$ の量を $f_j$ とします。流れ $j$ が通る経路上のどこかに施設があれば、その流れは施設を利用できます（捕捉する といいます）。施設を $p$ 個置いて、捕捉する流れの量の合計を最大にしてください。
§1 のグラフに 3 本の流れがあるとします。各流れは最短路（§2）を通るものとします。
| 流れ $j$ | 出発ノード → 到着ノード | 経路 $N_j$ | 量 $f_j$ |
|---|---|---|---|
| 1 | $1 \to 6$ | $1, 2, 3, 4, 6$ | $50$ |
| 2 | $3 \to 5$ | $3, 5$ | $30$ |
| 3 | $1 \to 5$ | $1, 2, 3, 5$ | $20$ |
記号は、流れの集合 $J = \{1, 2, 3\}$、流れ $j$ が通るノードの集合 $N_j$（表の経路の列）、施設を置ける場所 $V$（すべてのノード）です。決めることは 2 種類あり、どちらも 0-1 変数です。
$$ x_i = \begin{cases} 1 & \text{ノード } i \text{ に施設を置く} \\ 0 & \text{置かない} \end{cases}, \quad i \in V, \qquad y_j = \begin{cases} 1 & \text{流れ } j \text{ を捕捉する} \\ 0 & \text{捕捉しない} \end{cases}, \quad j \in J $$
定式化は次のとおりです。
$$ \begin{aligned} & z = \sum_{j \in J} f_j y_j \rightarrow \max, \\ \text{s.t.} \quad & \sum_{i \in N_j} x_i \ge y_j, \quad \forall j \in J, \\ & \sum_{i \in V} x_i = p, \\ & x_i \in \{0, 1\}, \ \forall i \in V, \qquad y_j \in \{0, 1\}, \ \forall j \in J. \end{aligned} $$
1 本目の制約は「流れ $j$ の経路上のどこかに施設があるときだけ、$y_j = 1$ にできる」です。流れ 1 で展開すると、$N_1 = \{1, 2, 3, 4, 6\}$ なので
$$ x_1 + x_2 + x_3 + x_4 + x_6 \ge y_1 $$
です。経路上に施設が 1 つもなければ左辺が $0$ なので $y_1 = 0$ になり、捕捉した流れに数えられません。2 本目の制約は「施設はちょうど $p$ 個」です。第 5 回の別冊のビンパッキング問題で、$y_i$ を不等式で縛ったのと同じ型です。
この例で $p = 1$ なら、ノード $3$ に置くと 3 本の流れすべてを捕捉でき、$z^* = 100$ です（ノード $2$ では流れ 2 を捕捉できず $70$ です）。上の問題設定の図を最適化すると、次の図になります。
この問題も、定式化さえできれば §4 と同じように PuLP で解けます。
5.2 教訓：定式化できればソルバーで解ける。しかし¶
今回の 3 つの問題（最短路、最大フロー、施設配置）も、第 5 回のナップサック問題・ビンパッキング問題も、定式化さえできればソルバーが解いてくれました。定式化は「決定変数 → 目的関数 → 制約条件」（第 3 回 §2）と、記法（第 1 回）の積み重ねでできています。これがこの授業で一番伝えたかったことです。
しかし、常に整数計画問題として解くのが正しいわけではありません。
- 最短路問題には ダイクストラ法 という専用の解き方があります。カーナビの地図はノードが数百万個ありますが、ダイクストラ法は一瞬で最短路を出します。§2 の定式化で解くと、変数がエッジの数（数百万個）だけでき、ソルバーでは桁違いに時間がかかります。
- もう 1 つ例を挙げます。閉路を含まず、すべてのノードがつながるようなエッジの集合を 全域木 と呼びます。最小全域木問題 は、全域木のうちコストの合計が最小のものを求める問題です（ネットワークの配線、水道管の敷設など）。この問題は、「コストの小さいエッジから順に、閉路ができないものを選ぶ」という 貪欲法 で必ず最適解になります。
第 5 回 §4.3 で、ナップサック問題の貪欲法には最適解の保証がないことを見ました。同じ貪欲法でも、最小全域木問題では保証があります。違いは問題の 構造 です。
道具は問題の構造で選びます。 まず定式化して問題の形を見ます。最短路・最小全域木のように専用の速い方法がある形なら、それを使います。ナップサック・ビンパッキング・施設配置のように専用の方法がない形なら、整数計画のソルバーに任せます。どちらにしても、出発点は「定式化できること」です。
5.3 この授業の流れ¶
| 回 | 学んだこと |
|---|---|
| 第 1 回 | 記法：集合、添字、$\sum$、$\forall$（式を 読む） |
| 第 3 回 | 線形計画問題の定式化：決定変数、目的関数、制約条件、図による解法（書く） |
| 第 4 回 | 線形計画問題の解法：標準形、基底解、単体法（解く） |
| 第 5 回 | 整数計画問題の定式化と解法：0-1 変数、分枝限定法、ソルバー |
| 第 6 回 | グラフ上の最適化問題の定式化と解法比較：フロー保存制約、アルゴリズム（道具を 選ぶ） |
読めるようになり、書けるようになり、解けるようになり、最後に道具を選べるようになる、という順番でした。
6. 演習¶
今回のまとめ
- グラフはノードの集合 $V$ とエッジの集合 $E$ で表し、コスト $c_{ij}$・容量 $u_{ij}$ は「行がノード $i$、列がノード $j$」の表で与える。無向のエッジは向きの違う 2 本 $(i, j)$、$(j, i)$ で表す。ノード $k$ から出るエッジは $k$ 行の $x_{kj}$、入るエッジは $k$ 列の $x_{ik}$（§1）。
- 最短路問題：0-1 変数 $x_{ij}$、目的関数 $\sum_{(i, j) \in E} c_{ij} x_{ij} \rightarrow \min$、フロー保存制約「出る − 入る $= 1, -1, 0$」。整数計画問題（§2）。
- 最大フロー問題：流量 $x_{ij}$（実数）と流す量 $f$、容量制約 $0 \le x_{ij} \le u_{ij}$、フロー保存制約「出る − 入る $= f, -f, 0$」、$f \rightarrow \max$。線形計画問題（§3）。
- 定式化できればソルバーで解ける。しかし専用の方法（ダイクストラ法、最小全域木の貪欲法）がある問題ではそちらが桁違いに速い。道具は問題の構造で選ぶ（§5）。
演習問題は別紙（06_problem）にあります。解答用紙に記入して提出してください（解答用紙のみ回収。出席確認を兼ねます）。PuLP のノートブック 06_pulp.ipynb は配布のみで、提出はありません。
- 最短路問題（§1〜§2。解答用紙の表）。講義とは別の無向グラフ（ノード 6 個、エッジ 8 本）について、目的関数を展開して書く、出発ノードと指定した途中ノードのフロー保存制約を展開して書く、最短路とそのコストを求める。
- 最大フロー問題（§3。解答用紙の裏）。同じグラフに容量が与えられる。指定したエッジの容量制約、指定した途中ノードと出発ノードのフロー保存制約を書き、最大フローの値と各エッジの流れ（向きと量）を求める。
式は表の行・列から拾って書きます。無向のエッジは 2 本に分けるので、ノード $k$ の式には $k$ 行の変数と $k$ 列の変数の両方が現れます。最短路と最大フローは目視で求め、§3.1 の方法（境目をまたぐエッジの容量の和）で「これ以上は無理」を確かめてください。
次回は演習の解説とまとめです。
参考文献¶
- 福島雅夫『新版 数理計画入門』朝倉書店、2011。
- 梅谷俊治『しっかり学ぶ数理最適化 モデルからアルゴリズムまで』講談社、2020。
付録：用語早見表¶
| 用語 | 意味 | 本資料の節 |
|---|---|---|
| グラフ | ノード（点）とエッジ（線）でできた図 | §1.1 |
| 無向グラフ・有向グラフ | エッジに向きがない（両方向に通れる）・向きがある（一方通行）。無向のエッジ $\{i, j\}$ は $(i, j)$ と $(j, i)$ の 2 本で表す | §1.2 |
| ノード $i \in V$ | グラフの点。番号で呼ぶ。$V$ はノードの集合 | §1.3 |
| エッジ $(i, j) \in E$ | ノード $i$ からノード $j$ への線（向き付き）。$E$ はエッジの集合 | §1.3 |
| コスト $c_{ij}$、容量 $u_{ij}$ | エッジ $(i, j)$ の数値。行が $i$、列が $j$ の表で与える（無向なら対称） | §1.3、§1.4 |
| 出るエッジ・入るエッジ | ノード $k$ から出る $(k, j)$ は表の $k$ 行、入る $(i, k)$ は $k$ 列 | §1.5 |
| $\sum_{j : (k, j) \in E} x_{kj}$、$\sum_{i : (i, k) \in E} x_{ik}$ | 出るエッジの和（$i = k$ に固定し $j$ で足す）、入るエッジの和（$j = k$ に固定し $i$ で足す） | §1.5 |
| 隣接行列 | ノードの接続関係を 0 と 1 で表した $n \times n$ の行列（この授業では表のまま扱う） | §1.4 |
| 最短路問題 | 出発ノードから到着ノードへの、コストの合計が最小の経路を求める。整数計画問題 | §2 |
| フロー保存制約 | 各ノードで「出る − 入る $=$ 右辺」。右辺は出発ノード $1$、到着ノード $-1$、途中 $0$（最大フローでは $f$、$-f$、$0$） | §2.4、§3.3 |
| 最大フロー問題 | 容量を守って、出発ノードから到着ノードへ流せる量 $f$ を最大にする。線形計画問題 | §3 |
| 容量制約 | $0 \le x_{ij} \le u_{ij}$ | §3.3 |
| 辞書（PuLP） | エッジ (i, j) をキーにしてグラフのデータを持つ |
§4.1 |
| 施設配置（流れの捕捉） | 施設を $p$ 個置き、経路上に施設がある流れの量を最大にする | §5.1 |
| ダイクストラ法 | 最短路問題の専用の解き方。ソルバーより桁違いに速い | §5.2 |
| 経路 | $s$ から $t$ へ、エッジをたどって進むノードの列（同じノードは 2 度通らない） | §2.1 |
| 閉路 | 始点と終点が同じノードになる経路 | §2.1 |
| 全域木 | 閉路を含まず、すべてのノードがつながるエッジの集合 | §5.2 |
| 最小全域木問題 | 全域木のうちコストの和が最小のもの。貪欲法で最適 | §5.2 |