最適輸送の整数解

導入

2つの整数値のベクトル$\mathbf{a}=(a_i)_i \in \mathbb{Z}_{\geq 0}^n$, $\mathbf{b}=(b_j)_j \in \mathbb{Z}_{\geq 0}^m$と，$i$と$j$の輸送コストを$c_{ij} \in \mathbb{R}$とします．このとき，最適輸送行列は整数解として取れます．今回は，この主張の詳細と，最適輸送問題と整数計画版の最適輸送問題との等価性，及び，証明のスケッチについて述べます．

最適輸送問題と主張

まず，主張を述べる前に，最適輸送について復習します．最適輸送問題とは，次の輸送行列$\mathbf{p} = (p_{ij})_{ij}$を求めることです．

$$\argmin_{\mathbf{p} \in \Pi (\mathbf{a},\mathbf{b})} \sum_{ij} c_{ij} p_{ij} .$$

ここで，$\Pi (\mathbf{a},\mathbf{b})$は輸送多面体，つまり，

$$\Pi (\mathbf{a},\mathbf{b}) = \left\{ \mathbf{p} = (p_{ij})_{ij} \in \mathbb{R}^{nm} \, \middle| \, p_{ij} \geq 0 ; \forall j , \sum_i p_{ij} = b_j ; \forall i , \sum_j p_{ij} = a_i \right\} .$$

主張の準備が整ったので，今回の主定理を述べます．

定理 1.　ベクトルを$\mathbf{a} \in \mathbb{Z}_{\geq 0}^n$, $\mathbf{b} \in \mathbb{Z}_{\geq 0}^m$, $\mathbf{c} = (c_{ij})_{ij} \in \mathbb{R}^{nm}$とします．このとき，最適輸送問題の解は$\mathbf{p} \in \mathbb{Z}^{nm}$と取れます．

最適輸送問題と整数計画版の最適輸送問題との等価性

整数計画版の最適輸送問題とは，

$$\argmin_{\mathbf{p} \in \Pi_{\mathbb{Z}} (\mathbf{a},\mathbf{b})} \sum_{ij} c_{ij} p_{ij} .$$

ここで，$\Pi_{\mathbb{Z}} (\mathbf{a},\mathbf{b})$は

$$\Pi_{\mathbb{Z}} (\mathbf{a},\mathbf{b}) = \left\{ \mathbf{p} = (p_{ij})_{ij} \in \mathbb{Z}^{nm} \, \middle| \, p_{ij} \geq 0 ; \forall j , \sum_i p_{ij} = b_j ; \forall i , \sum_j p_{ij} = a_i \right\} .$$

最適輸送問題と整数計画版の最適輸送問題は定理 1から等価であることがわかります．

定理 2.
ベクトルを$\mathbf{a} \in \mathbb{Z}_{\geq 0}^n$, $\mathbf{b} \in \mathbb{Z}_{\geq 0}^m$, $\mathbf{c} = (c_{ij})_{ij} \in \mathbb{R}^{nm}$とします．このとき，

$$\min_{\mathbf{p} \in \Pi (\mathbf{a},\mathbf{b})} \sum_{ij} c_{ij} p_{ij} = \min_{\mathbf{p} \in \Pi_{\mathbb{Z}} (\mathbf{a},\mathbf{b})} \sum_{ij} c_{ij} p_{ij} .$$

定理2は，ボールの個数のように，整数でしか輸送できない場合でも，実数の輸送と考えて解いて良いことを意味します．

証明のスケッチ

輸送多面体は次のように書けます：

$$\Pi (\mathbf{a},\mathbf{b}) = \left\{ \mathbf{p} = (p_{ij})_{ij} \in \mathbb{R}^{nm} \, \middle| \, p_{ij} \geq 0 ; \mathbf{A} \mathbf{p} = \begin{pmatrix} \mathbf{a} \\ \mathbf{b} \end{pmatrix} \right\} .$$

ここで，

$$\mathbf{A} = \begin{pmatrix} \mathbf{1}_n^{\top} \otimes \mathrm{Id}_m \\ \mathrm{Id}_n \otimes \mathbf{1}_m^{\top} \end{pmatrix},$$

$\mathrm{Id}_n$はサイズが$n$の行列であり，$\mathbf{1}_n$はサイズが$n$の$1$が並んでいるベクトルです．

天下り的ですが，完全単模行列の定義を与えます．

定義 3. (cf. [MS2013, p117]) (正方形とは限らない)整数行列は，任意の小行列式の値が$0,1,-1$のいずれかであるとき，完全単模(たんも)行列(totally unimodular matrix)と呼びます．

制約条件に現れる行列が完全単模行列であるとき，線形計画の制約条件の整数性が最適解に遺伝することが知られています．

命題 4. (cf. [MS2013, 定理 4.17]) 行列$A\in\mathbb{Z}^{nm}$は完全単模行列であり，$b \in \mathbb{Z}^n$，$c \in \mathbb{R}^m$とします．このとき，線形計画問題

$$\min_{\substack{Ax = b \\ x \geq 0}} c^{\top}x$$

は整数解$x \in \mathbb{Z}^m$を持ちます．

実は，行列$\mathbf{A}$は完全単模行列であることがわかります．これは，練習問題とします．
命題4から，定理1が従います．

参考文献

[YCor2020] YCor, integer solution of optimal transport, mathoverflow, (2020).

[MS2013] 室田一雄, 杉原正顕, 東京大学工学教程 基礎系 数学 線形代数II, 丸善出版, (2013).