この記事について
過去に整数計画の記事で、最小全域木やTSPをグラフの問題として定式化しました。そのときに 完全単模行列（TU行列） の話をして「接続行列がTUなら、整数変数を使わなくてもLPを解くだけで整数解が出てくる」的な話もしました。
ただ、あれは「そういう性質がある」で終わっていて、 じゃあ実際にネットワークの問題をどう解くのか といった話題にはあまり踏み込めていませんでした。
というわけで、ネットワーク最適化を腰を据えて扱うシリーズを始めます。全16記事とかなり長いですが、構成は単純です。
- 第1部（①〜⑧） ：問題を LP・整数計画に定式化して、ソルバーに投げて解く
- 第2部（⑨〜⑯） ：同じ問題を 専用のアルゴリズムで解く
同じ問題を2通りのやり方で解いて、 答えが一致することを毎回確認します 。「定式化すれば何でも解けるのに、なぜ専用アルゴリズムがあるのか」「専用アルゴリズムがあるのに、なぜ定式化するのか」という疑問に、両方やることで答えたいなと思っています。
ソルバーは PuLP（CBC） を使います。無料なので手元でそのまま試せます。第2部のアルゴリズムはすべてスクラッチ実装するので、外部ライブラリは不要です。
シリーズの構成
第1部：定式化編（LP・整数計画で解く）
| 記事 | 内容 |
|---|---|
| ①（本記事） | ネットワーク最適化とは？最短路をLPで解く |
| ② | 最大流問題をLPで解く |
| ③ | 最小カットと最大流最小カット定理 |
| ④ | 最小費用流問題 ─ ネットワーク問題の親玉 |
| ⑤ | 割当問題・マッチング ─ なぜ整数解が出るのか |
| ⑥ | 資源制約付き最短路 ─ 整数性が壊れる瞬間 |
| ⑦ | Steiner木問題 |
| ⑧ | 多品種流問題 |
第2部：アルゴリズム編（専用アルゴリズムで解く）
| 記事 | 内容 |
|---|---|
| ⑨ | ダイクストラ法 |
| ⑩ | ベルマン-フォード法と負閉路 |
| ⑪ | Yenのアルゴリズムで K 本の最短路を列挙 |
| ⑫ | フォード・ファルカーソン法と最小カットの取り出し |
| ⑬ | 逐次最短路法で最小費用流を解く |
| ⑭ | ハンガリアン法 |
| ⑮ | Steiner木の2近似アルゴリズム |
| ⑯ | 多品種流のラグランジュ緩和＋シリーズまとめ |
ネットワーク最適化とは
ネットワーク最適化は、ざっくり言うと
「グラフの上を『何か』が流れる問題」
を扱う分野です。「何か」は、荷物だったり、電流だったり、データだったり、人だったりします。
グラフ最適化（TSPや最小全域木など）と何が違うのかというと、ネットワーク最適化では 枝に「流量」という連続量が乗る のが特徴です。この「流れ」という見方をすると、一見バラバラに見える問題が全部同じ形に書けてしまいます。
| 問題 | 何が流れるか | どこからどこへ |
|---|---|---|
| 最短路問題 | 1単位の荷物 | 始点から終点へ |
| 最大流問題 | できるだけ多くの荷物 | 始点から終点へ |
| 最小費用流問題 | 決められた量の荷物 | 始点から終点へ（費用最小で） |
| 割当問題 | 1単位ずつの「担当」 | 人から仕事へ |
| 輸送問題 | 製品 | 工場から店舗へ |
このシリーズで一番強調したいのはここです。 これらは全部、同じ「フロー」の枠組みで書けます 。
このシリーズで使う共通ネットワーク
全16記事で、同じネットワークを使い回します。毎回同じ図が出てくるので、だんだん見慣れてくるはずです。
- ノードは A〜F の6個。 A が始点（source）、F が終点（sink）
- 枝のラベルは「 費用 / 容量 」。費用は1単位流すのにかかるお金、容量は最大で何単位流せるか
表にすると以下のとおりです。
| 枝 | 費用 | 容量 |
|---|---|---|
| A→B | 2 | 5 |
| A→C | 4 | 5 |
| B→C | 1 | 2 |
| B→D | 7 | 3 |
| C→D | 3 | 2 |
| C→E | 5 | 3 |
| D→F | 2 | 6 |
| E→D | 1 | 1 |
| E→F | 6 | 4 |
Pythonでは以下のように持っておきます。この定義は以降の全記事で使い回します。
NODES = ['A', 'B', 'C', 'D', 'E', 'F']
SOURCE, SINK = 'A', 'F'
# 枝：(始点, 終点) -> (費用, 容量)
ARCS = {
('A', 'B'): (2, 5),
('A', 'C'): (4, 5),
('B', 'C'): (1, 2),
('B', 'D'): (7, 3),
('C', 'D'): (3, 2),
('C', 'E'): (5, 3),
('D', 'F'): (2, 6),
('E', 'D'): (1, 1),
('E', 'F'): (6, 4),
}
COST = {a: c for a, (c, _) in ARCS.items()}
CAP = {a: u for a, (_, u) in ARCS.items()}
def out_arcs(v):
"""vから出る枝"""
return [a for a in ARCS if a[0] == v]
def in_arcs(v):
"""vに入る枝"""
return [a for a in ARCS if a[1] == v]
最短路問題を「流れ」として書く
最短路問題は「A から F まで、費用の合計が最小になる経路を見つけよ」という問題です。
これを流れとして言い換えると、
「A から 1単位の荷物を出して、F で 1単位受け取る。途中のノードでは荷物が消えたり湧いたりしない。このとき輸送費用を最小にせよ」
となります。1単位の荷物がたどった経路が、そのまま最短路になるわけです。
フロー保存則
「途中のノードで荷物が消えたり湧いたりしない」という条件を式にしたものが フロー保存則（flow conservation） です。
各ノード $v$ について、
\underbrace{\sum_{a \in \delta^+(v)} x_a}_{v \text{ から出ていく量}}
- \underbrace{\sum_{a \in \delta^-(v)} x_a}_{v \text{ に入ってくる量}}
= b_v
ここで $\delta^+(v)$ は $v$ から出る枝の集合、$\delta^-(v)$ は $v$ に入る枝の集合です。$b_v$ は「そのノードで荷物が湧く量」で、
b_v = \begin{cases}
+1 & (v = A：1単位を送り出す) \\
-1 & (v = F：1単位を受け取る) \\
0 & (それ以外：素通り)
\end{cases}
とします。
定式化
これで最短路問題の定式化ができます。
\begin{aligned}
\text{最小化} \quad & \sum_{a \in A} c_a x_a \\
\text{条件} \quad & \sum_{a \in \delta^+(v)} x_a - \sum_{a \in \delta^-(v)} x_a = b_v \quad (\forall v \in V) \\
& x_a \ge 0 \quad (\forall a \in A)
\end{aligned}
ここで注目してほしいのは、 $x_a$ が 0-1 変数ではなく、ただの非負の連続変数 だということです。
「その枝を使うか使わないか」を表すなら $x_a \in {0, 1}$ にしたくなりますよね。でも、この問題ではその必要がありません。 LPとして解いても、勝手に0か1の答えが返ってきます 。
なぜそうなるのかというと、この制約行列（グラフの接続行列）が 完全単模（TU） だからです。整数計画シリーズの「整数性を持つ整数計画問題」で扱った性質が、ここで効いてきます。この話は⑤でじっくり扱うので、今は「そういうものらしい」と思って先に進んでください。
PuLPで解いてみる
実装します。制約に名前を付けているのは、後で双対変数を取り出すためです。
import pulp
prob = pulp.LpProblem('shortest_path', pulp.LpMinimize)
# 0-1変数ではなく、ただの非負連続変数にする
x = {a: pulp.LpVariable(f'x_{a[0]}{a[1]}', lowBound=0) for a in ARCS}
# 目的関数：費用の合計
prob += pulp.lpSum(COST[a] * x[a] for a in ARCS)
# フロー保存則
for v in NODES:
b = 1 if v == SOURCE else (-1 if v == SINK else 0)
prob += (pulp.lpSum(x[a] for a in out_arcs(v))
- pulp.lpSum(x[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'{a[0]}->{a[1]}': x[a].value()
for a in ARCS if x[a].value() > 1e-9})
状態=Optimal 最短路長=8.0
使われた枝: {'A->B': 1.0, 'B->C': 1.0, 'C->D': 1.0, 'D->F': 1.0}
A→B→C→D→F で長さ 8 が最短路でした。連続変数で解いたのに、値はきっちり 1.0 になっています。
図で見るとこうです。
- 赤い太線 ：最短路 A→B→C→D→F
- 青い d=◯ ：A からそのノードまでの最短距離
一応、手で確かめておきましょう。A→F の経路は全部で7本あります。
A→B→C→D→F = 2+1+3+2 = 8 ← 最短
A→C→D→F = 4+3+2 = 9
A→B→D→F = 2+7+2 = 11
A→B→C→E→D→F = 2+1+5+1+2 = 11
A→C→E→D→F = 4+5+1+2 = 12
A→B→C→E→F = 2+1+5+6 = 14
A→C→E→F = 4+5+6 = 15
たしかに 8 が最小です。
双対変数を見ると「ポテンシャル」が出てくる
個人的にここからが面白いところです。以前双対問題の記事を書きましたが、「双対変数には意味がある（潜在価格）」という話をしました。今回の 最短路問題の双対変数にも、はっきりした意味があります 。
フロー保存則の制約に対応する双対変数を $y_v$ と呼びます（各ノードに1つずつ付きます）。取り出してみましょう。
raw = {v: prob.constraints[f'flow_{v}'].pi for v in NODES}
print(f'{"ノード":<8}{"CBCの生値":>10}{"y_A=0に正規化":>14}{"A からの最短距離":>16}')
for v in NODES:
norm = raw[v] - raw[SOURCE]
print(f'{v:<8}{raw[v]:>10.1f}{norm:>14.1f}{-norm:>16.1f}')
ノード CBCの生値 y_A=0に正規化 A からの最短距離
A 3.0 0.0 -0.0
B 1.0 -2.0 2.0
C 0.0 -3.0 3.0
D -3.0 -6.0 6.0
E -5.0 -8.0 8.0
F -5.0 -8.0 8.0
CBCが返す生の値は定数分だけずれていますが（双対解は定数を足しても最適性が変わりません）、$y_A = 0$ になるように正規化すると、
$-y_v$ が、そのまま A から $v$ への最短距離になっています。
A=0、B=2、C=3、D=6、E=8、F=8。図の青い数字と一致していますね。
この $y_v$ を ポテンシャル（potential） と呼びます。「そのノードの標高」みたいなイメージです。
ポテンシャルが満たす性質
双対問題を実際に書き下すと、こうなります。
\begin{aligned}
\text{最大化} \quad & y_A - y_F \\
\text{条件} \quad & y_u - y_v \le c_{uv} \quad (\forall (u,v) \in A)
\end{aligned}
制約 $y_u - y_v \le c_{uv}$ は、言葉にすると
「隣り合うノードのポテンシャルの差は、その枝の費用を超えられない」
という意味です。$-y$ を距離だと思うと、$d_v \le d_u + c_{uv}$ となり、これは 三角不等式 そのものです。「A から v へ行くなら、u を経由するより遠くはならない」ということですね。
さらに、相補性条件（双対シリーズ⑦で扱ったやつです）から、
最短路上の枝では $y_u - y_v = c_{uv}$ が成り立つ（等号になる）
が言えます。実際に確認してみましょう。
| 枝 | $c_{uv}$ | $-y_u$ | $-y_v$ | $-y_v - (-y_u)$ | 判定 |
|---|---|---|---|---|---|
| A→B | 2 | 0 | 2 | 2 | 等号 （最短路上） |
| B→C | 1 | 2 | 3 | 1 | 等号 （最短路上） |
| C→D | 3 | 3 | 6 | 3 | 等号 （最短路上） |
| D→F | 2 | 6 | 8 | 2 | 等号 （最短路上） |
| A→C | 4 | 0 | 3 | 3 | 3 < 4 なので余裕あり |
| B→D | 7 | 2 | 6 | 4 | 4 < 7 なので余裕あり |
| C→E | 5 | 3 | 8 | 5 | 等号 （別の最短路上） |
| E→D | 1 | 8 | 6 | -2 | -2 < 1 |
| E→F | 6 | 8 | 8 | 0 | 0 < 6 |
きれいに分かれました。 最短路に使われている枝だけが等号 になっています（C→E も「A→B→C→E」という E への最短路の一部なので等号です）。
このポテンシャルという概念は、第2部の⑬（最小費用流の逐次最短路法）で本格的に使うことになります。ここで頭出しだけしておきました。
「LPで解ける」のは何が嬉しいのか
最短路にはダイクストラ法という有名な専用アルゴリズムがあります（⑨で扱います）。速さで言えばダイクストラ法の圧勝です。ではなぜLPで解くのでしょうか。
理由は 制約を足すのが簡単だから です。
例えば「途中で通れるノードは3つまで」「特定の枝を通るなら別の枝も通らないといけない」といった条件が付いたとき、ダイクストラ法はそのままでは使えません。アルゴリズムを作り直す必要があります。
一方、定式化しておけば 制約を1行足すだけ です。⑥で実際にそれをやります（そして、そこで整数性が壊れます）。
| 定式化して解く | 専用アルゴリズム | |
|---|---|---|
| 速度 | 遅い | 圧倒的に速い |
| 制約の追加 | 1行書き足すだけ | アルゴリズムの作り直し |
| 実装量 | 少ない | 多い |
| 大規模問題 | 苦しい | 得意 |
「まず定式化して解いてみて、遅かったら専用アルゴリズムを考える」 というのが実務的な順序かなと思います。
まとめ
- ネットワーク最適化は「グラフの上を何かが流れる」問題 。最短路も最大流も割当も、全部フローの言葉で書ける
- フロー保存則 （出ていく量 − 入ってくる量 = 湧き出し量）が定式化の中心
- 最短路は 0-1変数を使わずLPで解ける 。接続行列がTUだから（詳しくは⑤で）
- 双対変数はポテンシャル （始点からの最短距離）になる。最短路上の枝では相補性から等号が成り立つ
- LPで解く利点は速度ではなく、 制約を足すのが簡単なこと
次回②は最大流問題をLPで解きます。同じフロー保存則で、目的関数と制約をちょっと変えるだけで別の問題になる、というのを見ていきます。
参考にした記事や本、論文等
- R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, "Network Flows: Theory, Algorithms, and Applications," Prentice Hall, 1993.
- PuLP ドキュメント