この記事について

整数計画問題は一般に NP困難で、変数100個でも解けないことがあるくらい難しい問題です。しかし不思議なことに、「整数計画問題なのに、LP緩和を解くだけで自動的に整数解が出てくる」 特殊なクラスがあります。

その正体が 完全単模行列（Totally Unimodular Matrix; TU行列） です。最短路問題・最大流問題・割当問題などの古典的な組合せ最適化問題が高速に解ける理由はここに由来しているので、押さえておくと「なぜこの問題は簡単で、あの問題は難しいのか」が見えてくると思います。

※半分振り返り＆自己理解として書いてるので間違えてるところあるかもですが、ご容赦ください。（ご指摘いただけると嬉しいです。）

LP緩和の最適解が整数になることがある

通常、整数計画問題（IP）の LP緩和を解くと、最適解は小数になります。これを整数解に切り上げ・切り下げするだけでは元の問題の最適解にならないため、分枝限定法などの探索が必要です。

ところが、LP緩和を単体法で解いた基底解がそのまま整数になる問題クラス があります。このとき LP を解くだけで整数最適解が手に入るので、整数計画問題でありながら多項式時間で解ける ことになります。

その十分条件が「制約行列が完全単模行列」というものです。

単模行列と完全単模行列

単模行列（Unimodular Matrix）

単模行列：行列式の値が $\pm 1$ の整数正方行列。

例

\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad
\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \quad
\begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix} \quad (\det = 1)

完全単模行列（Totally Unimodular Matrix; TU行列）

完全単模行列：整数行列 $\mathbf{A}$ の 任意の正方部分行列 $\mathbf{B}$ の行列式が $0, \pm 1$ になる行列。

「任意の」というのが強い条件です。1×1部分行列の行列式は要素そのものなので、TU行列の全要素は $0, \pm 1$ に限られます。

例：

\mathbf{A} = \begin{pmatrix} 1 & 0 & 1 \\ -1 & 1 & 0 \\ 0 & -1 & 0 \end{pmatrix}

全要素が $0, \pm 1$ で、すべての正方部分行列の行列式が $0, \pm 1$ になります（実際に計算してみると分かります）。

なぜ TU行列だと整数解が出るのか

線形計画問題 $\min{\mathbf{c}^\top \mathbf{x} \mid \mathbf{A}\mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}}$ の最適基底解は：

\mathbf{x}_B^* = \mathbf{B}^{-1} \mathbf{b}

ここで $\mathbf{B}$ は最適基底行列です（単体法シリーズで扱いました）。$\mathbf{A}$ を「基底変数の列」$\mathbf{B}$ と「非基底変数の列」$\mathbf{N}$ に分割した形をイメージしてください。

もし $\mathbf{A}$ が完全単模行列なら：

$\mathbf{B}$（$\mathbf{A}$ の正方部分行列）の行列式は $\pm 1$
$\mathbf{B}^{-1}$ の各要素は $(\det \mathbf{B})^{-1} \cdot (\text{余因子行列})$ なので、整数になる
$\mathbf{b}$ が整数ベクトルなら、$\mathbf{B}^{-1} \mathbf{b}$ も整数ベクトル

つまり、最適基底解が自動的に整数になるわけです。

逆に言えば、整数条件を外して LP として解いても、もとの整数計画問題の最適解が得られる ので、強力な性質と言えます。

TU行列の十分条件

任意の整数行列が TU かどうかを判定するのは一般に難しい（多項式時間ではできるが実用的ではないらしい）ですが、いくつかの十分条件が知られています。

条件1：有向グラフの接続行列はTU

有向グラフ $G = (V, E)$ の 接続行列（incidence matrix） $\mathbf{A}$ は以下で定義されます。

行：頂点 $V$
列：辺 $E$
辺 $e = (u, v)$ について、$A_{ue} = +1$、$A_{ve} = -1$、その他は 0

この接続行列は常に TU です。

具体例：

頂点 1 → 頂点 2  （辺 e_1）
頂点 2 → 頂点 3  （辺 e_2）

       e_1  e_2
   1 ┌ +1   0 ┐
A= 2 │ -1  +1 │
   3 └  0  -1 ┘

この性質のおかげで、有向グラフ上の以下の問題は LP で解けます：

最短路問題
最大流問題
最小費用流問題

条件2：2部グラフの接続行列はTU

無向グラフは一般には TU になりませんが、2部グラフの接続行列は TU です。

学生   クラス
 i    │   j
 ●────●────●

学生とクラス間のマッチング行列がこれに該当します。

このため、以下の問題も LP で解けます：

2部マッチング問題
割当問題（Assignment Problem）

例：最短路問題のLP定式化

最短路問題（始点 $s$ から終点 $t$ への最短路を求める）を整数計画として定式化します。

定式化

\begin{aligned}
\text{minimize} \quad & \sum_{e \in E} d_e x_e \\
\text{subject to} \quad & \sum_{e \in \delta^+(s)} x_e = 1 \quad (s \text{ から出る辺は1本}) \\
& \sum_{e \in \delta^-(t)} x_e = 1 \quad (t \text{ に入る辺は1本}) \\
& \sum_{e \in \delta^+(v)} x_e - \sum_{e \in \delta^-(v)} x_e = 0 \quad (\text{中間頂点での流量保存}) \\
& x_e \in \{0, 1\}
\end{aligned}

ここで $\delta^+(v)$ は頂点 $v$ から出る辺、$\delta^-(v)$ は $v$ に入る辺の集合です。

制約行列

この問題の制約行列は有向グラフの接続行列そのもの（に右辺データを付けた形）になります。有向グラフの接続行列はTUなので、$x_e$ の整数条件を外して LP で解いても整数解が得られます。

PuLPで確認

import pulp

# 有向グラフ：辺 (始点, 終点, 距離)
edges = [
    (1, 2, 4), (1, 5, 2), (2, 3, 2), (2, 5, 1),
    (3, 4, 4), (3, 6, 1), (5, 6, 1), (6, 7, 2),
    (4, 7, 5), (3, 7, 4),
]
s, t = 1, 7

# 連続変数で LP として定式化
prob = pulp.LpProblem("shortest_path", pulp.LpMinimize)
x = {(u, v): pulp.LpVariable(f"x_{u}_{v}", lowBound=0, upBound=1)
     for (u, v, d) in edges}

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

# 各頂点での流量制約
all_nodes = set([u for (u, _, _) in edges] + [v for (_, v, _) in edges])
for node in all_nodes:
    out_flow = pulp.lpSum(x[(u, v)] for (u, v, d) in edges if u == node)
    in_flow  = pulp.lpSum(x[(u, v)] for (u, v, d) in edges if v == node)
    if node == s:
        prob += out_flow - in_flow == 1
    elif node == t:
        prob += out_flow - in_flow == -1
    else:
        prob += out_flow - in_flow == 0

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

print(f"最短距離 = {pulp.value(prob.objective):.0f}")
print("使われた辺:")
for (u, v, d) in edges:
    val = pulp.value(x[(u, v)])
    if val and val > 0.5:
        print(f"  {u} -> {v}（距離 {d}）, x = {val:.2f}")

実行結果例：

最短距離 = 5
使われた辺:
  1 -> 5（距離 2）, x = 1.00
  5 -> 6（距離 1）, x = 1.00
  6 -> 7（距離 2）, x = 1.00

lowBound=0, upBound=1 の連続変数として LP で解いたにも関わらず、すべての変数がぴったり 0 か 1 になっています。これが TU行列の威力ですね。

例：割当問題

m人の学生を n個のクラスに、満足度 $p_{ij}$ を最大化するように割り当てる問題。

\begin{aligned}
\text{maximize} \quad & \sum_{i=1}^{m} \sum_{j=1}^{n} p_{ij} x_{ij} \\
\text{subject to} \quad & \sum_{j=1}^{n} x_{ij} = 1, \quad i = 1, \ldots, m \quad (\text{各学生はちょうど1つのクラス}) \\
& \sum_{i=1}^{m} x_{ij} \leq u_j, \quad j = 1, \ldots, n \quad (\text{各クラスの定員}) \\
& x_{ij} \in \{0, 1\}
\end{aligned}

この問題の制約行列も 2部グラフの接続行列構造 を持つので TU です。$x_{ij}$ の整数条件を外しても整数解が得られます。

実務上はハンガリー法などのより効率的なアルゴリズムが知られていますが、追加の制約条件（特定の学生は同じクラスに入れない等）を入れたい場合は LP/MIP として解くと柔軟性が高まります。

TU性が壊れるケース

注意点として、以下のようなケースでは TU性が壊れて整数解が出なくなります。

ケース1：無向グラフの接続行列

無向グラフの接続行列は、グラフが 2部グラフでない場合（奇閉路を含む場合）に TU でなくなります。

例：三角形 $K_3$ の接続行列の行列式は $\pm 2$ になり、TU の条件を満たしません。（簡単な解説は次回小休憩記事にて）

ケース2：追加の制約

最短路問題に「途中で必ず特定の頂点を通る」「総辺数を K 本以下にする」などの追加制約を入れると、TU性が壊れ、整数計画として分枝限定法が必要になります。

このため、現実問題では「TU性を壊さない範囲でモデリングする」or「TUが壊れることを覚悟して MIPソルバーに任せる」かのトレードオフが発生します。

まとめ

完全単模行列（TU行列）：任意の正方部分行列の行列式が $0, \pm 1$ の整数行列
制約行列が TU かつ右辺 $\mathbf{b}$ が整数なら、LP緩和の最適基底解が自動的に整数
有向グラフの接続行列はTU → 最短路問題・最大流問題・最小費用流問題
2部グラフの接続行列はTU → 2部マッチング問題・割当問題
追加制約や奇閉路などでTU性が壊れると、分枝限定法が必要になる