この記事について

整数計画でグラフ問題を扱おうとすると、「連結性をどう表現するか」ということを考えなければいけません。最小全域木やTSPの定式化を調べると「部分巡回路除去制約」「指数個の制約」「MTZ定式化」といった用語がたくさん出てきてあまり整理できてなかったのでこれを機に整理します。

この記事では、これらの定式化をできるだけ本質をとらえながら整理していきます。

グラフの連結性を表現する難しさ

最小全域木やTSPの定式化で最も難しいのは「選んだ辺の集合が連結である」「部分閉路を持たない」を線形制約で表現することです。

「辺をちょうど $|V|-1$ 本選ぶ」だけでは不十分で、追加の制約が必要です。

最小全域木：カット制約による定式化

問題

無向グラフ $G = (V, E)$、各辺 $e$ の長さ $d_e$ が与えられたとき、全頂点を連結する最短の辺集合 $T \subseteq E$ を求める問題。

定式化

\begin{aligned}
\text{minimize} \quad & \sum_{e \in E} d_e x_e \\
\text{subject to} \quad & \sum_{e \in E} x_e = |V| - 1 \quad (\text{辺の本数}) \\
& \sum_{e \in \delta(S)} x_e \geq 1, \quad S \subset V,\ S \neq \emptyset \quad (\text{カット制約}) \\
& x_e \in \{0, 1\}
\end{aligned}

ここで $\delta(S)$ は頂点集合 $S$ と $V \setminus S$ を繋ぐ辺の集合（カット）です。

「任意の非空真部分集合 $S$ について、$S$ と外側を繋ぐ辺が少なくとも1本ある」という条件が連結性を保証します。

制約が指数個

カット制約は $S$ が $V$ の 任意の非空真部分集合 なので、その数は $2^{|V|} - 2$ 本。

$\|V\|$	カット制約の数
10	1,022
20	約100万
30	約10億

最初から全部書き下すのは現実的ではありません。

解決策：切除平面法

すべての制約を最初から入れるのではなく、LP緩和を解いた結果に違反する制約だけを追加していくのが切除平面法です。

① 制約なし（か少数）でLPを解く
② 違反するカット制約があるか調べる（分離問題）
③ あれば追加して①へ
④ なければ最適

最小全域木の場合、違反するカット制約の発見は最小カット問題として多項式時間で解けるので、切除平面法が実用上機能します。

最小全域木：単一可換流による多項式個の定式化

別のアプローチとして、補助変数を導入して制約数を多項式に抑える方法もあります。

アイデア

グラフを有向化（辺 ${u, v}$ を $(u, v), (v, u)$ の2方向に分割）
適当な根 $r$ を選ぶ
各頂点 $v$ について「根からの辺数」を表す変数 $y_v$ を導入
「$v$ に入る辺がちょうど1本」「$u \to v$ が選ばれるなら $y_v = y_u + 1$」を強制

\begin{aligned}
\text{minimize} \quad & \sum_{(u,v) \in \tilde{E}} \tilde{d}_{uv} x_{uv} \\
\text{subject to} \quad & \sum_{u \in \delta^-(v)} x_{uv} = 1, \quad v \in V \setminus \{r\} \\
& y_u - y_v + |V| \cdot x_{uv} \leq |V| - 1, \quad (u, v) \in \tilde{E} \\
& x_{uv} \in \{0, 1\} \\
& y_r = 0, \quad 1 \leq y_v \leq |V| - 1
\end{aligned}

2本目の制約は「$x_{uv} = 1$ なら $y_u \leq y_v - 1$」を意味します。これにより閉路が禁止されます。

イメージとしては「根 $r$ から枝を伸ばして木を成長させる」感じです。各頂点には「親」が1つだけあり、$y_v$ は根からの深さを表します。

メリット・デメリット

観点	カット制約版	単一可換流版
制約数	指数	多項式
変数数	$\|E\|$	$\|E\| + \|V\|$
LP緩和の質	強い	弱い
実装	切除平面法が必要	直接書ける

LP緩和の質が落ちる点（下界が悪くなる）には注意が必要です。

巡回セールスマン問題（TSP）

問題

都市集合 $V$ と都市間距離 $d_{uv}$ が与えられたとき、全都市をちょうど1回ずつ訪問する最短の巡回路を求める問題。

DFJ定式化（部分巡回路除去）

最も古典的な定式化が Dantzig-Fulkerson-Johnson (1954) のものです。

\begin{aligned}
\text{minimize} \quad & \sum_{u \in V} \sum_{v \in V, v \neq u} d_{uv} x_{uv} \\
\text{subject to} \quad & \sum_{u \in V, u \neq v} x_{uv} = 1, \quad v \in V \quad (\text{各都市に入る辺は1本}) \\
& \sum_{u \in V, u \neq v} x_{vu} = 1, \quad v \in V \quad (\text{各都市から出る辺は1本}) \\
& \sum_{(u,v) \in E(S)} x_{uv} \leq |S| - 1, \quad S \subset V,\ |S| \geq 2 \quad (\text{部分巡回路除去}) \\
& x_{uv} \in \{0, 1\}
\end{aligned}

最初の2本だけだと、「全部の都市が訪問される」けど複数の小さな巡回路（部分巡回路）に分かれる可能性があります。

これを禁止するのが3本目の 部分巡回路除去制約（Subtour Elimination Constraint, SEC） です。「任意の頂点部分集合 $S$ 内部で完結する辺は高々 $|S|-1$ 本」を要求します。

制約数は最小全域木と同様に 指数個（$2^{|V|}$ オーダー） になるので、切除平面法を使うのが実用的です。

MTZ定式化（多項式個）

Miller-Tucker-Zemlin (1960) ではDFJの制約数を多項式に抑えた方法で定式化しています。

\begin{aligned}
\text{minimize} \quad & \sum_{u \in V} \sum_{v \in V, v \neq u} d_{uv} x_{uv} \\
\text{subject to} \quad & \sum_{u \neq v} x_{uv} = 1, \quad v \in V \\
& \sum_{u \neq v} x_{vu} = 1, \quad v \in V \\
& y_u - y_v + |V| \cdot x_{uv} \leq |V| - 1, \quad u, v \in V \setminus \{s\},\ u \neq v \\
& y_s = 0,\quad 1 \leq y_v \leq |V| - 1 \\
& x_{uv} \in \{0, 1\}
\end{aligned}

$y_v$ は「都市 $v$ を訪問する順番」を表す補助変数。

意味：
 x_{uv} = 1 なら u を訪問してから v を訪問
       → y_u + 1 ≤ y_v
   (i.e., y_u - y_v ≤ -1)

3本目の制約 y_u - y_v + |V| x_{uv} ≤ |V| - 1 で：

$x_{uv} = 1$ なら $y_u - y_v \leq -1$（順序強制）
$x_{uv} = 0$ なら $y_u - y_v \leq |V| - 1$（実質無効）

DFJの指数個の制約が、多項式個の制約 + 補助変数 $y_v$ に置き換わっています。

イメージで言うと、各都市に「訪問順 $y_v$」を振っておき、辺 $u \to v$ を選ぶたびに $y$ が必ず $+1$ 以上増えるようにしておきます。すると 部分巡回路を一周しようとすると $y$ が増え続けて自己矛盾するため、サイクルが閉じられません。

PuLPでMTZ定式化を実装

import pulp
import numpy as np

# ランダムな5都市
np.random.seed(0)
n = 5
coords = np.random.rand(n, 2) * 100
d = [[np.linalg.norm(coords[i] - coords[j]) for j in range(n)]
     for i in range(n)]

prob = pulp.LpProblem("tsp_mtz", pulp.LpMinimize)

# x_{uv}: u から v に直行するか
x = {(u, v): pulp.LpVariable(f"x_{u}_{v}", cat='Binary')
     for u in range(n) for v in range(n) if u != v}
# y_v: 訪問順序
y = [pulp.LpVariable(f"y_{v}", lowBound=0, upBound=n-1)
     for v in range(n)]

# 目的関数
prob += pulp.lpSum(d[u][v] * x[(u, v)] for u in range(n) for v in range(n) if u != v)

# 各都市に入る辺・出る辺は1本
for v in range(n):
    prob += pulp.lpSum(x[(u, v)] for u in range(n) if u != v) == 1
    prob += pulp.lpSum(x[(v, u)] for u in range(n) if u != v) == 1

# MTZ部分巡回路除去
s = 0  # 出発点
prob += y[s] == 0
for u in range(n):
    for v in range(n):
        if u != v and u != s and v != s:
            prob += y[u] - y[v] + n * x[(u, v)] <= n - 1

prob.solve(pulp.PULP_CBC_CMD(msg=0))

print(f"最短巡回路長 = {pulp.value(prob.objective):.2f}")
tour = [s]
current = s
while True:
    for v in range(n):
        if v != current and pulp.value(x[(current, v)]) > 0.5:
            tour.append(v)
            current = v
            break
    if current == s:
        break
print(f"巡回路: {' -> '.join(map(str, tour))}")

実行結果例：

最短巡回路長 = 158.71
巡回路: 0 -> 4 -> 1 -> 2 -> 3 -> 0

DFJ vs MTZ

観点	DFJ	MTZ
制約数	$O(2^n)$	$O(n^2)$
変数数	$O(n^2)$	$O(n^2)$ + $n$ 個の $y$
LP緩和の質	強い	弱い
実装の手間	切除平面法が必要	直接書ける

LP緩和の質が問題になります。実用上は：

小〜中規模（〜30都市）：MTZで直接解いてOK
大規模：DFJ + 切除平面法（実際の高性能TSPソルバーConcordeはこちらに近いらしいです。確か、、、。違ったらすみません。）

まとめ

最小全域木：カット制約（指数個・切除平面法）or 単一可換流（多項式個）
TSP：
- DFJ定式化：部分巡回路除去制約（指数個、LP緩和が強い）
- MTZ定式化：順序変数 $y_v$ で多項式個（実装が楽）
LP緩和の質と制約数のトレードオフがある