最小費用流問題を一般化して双対問題を綺麗に書きたい

最近ネットワークフローにハマっている（？）ので，勉強したことを書きます．一応競プロに役に立つ可能性がなくはないです．あと，簡単のために詳細な数学的議論を省略しているところがあります．

TL;DR

最小費用流問題は一般化すると双対関係が綺麗に書けるよ

最小費用流問題と双対問題

最小費用流問題とは，有効グラフ $G=(V, E)$ ，辺 $(i, j) \in E$ のコスト $c_{ij}$ ，辺 $i \in V$ の容量 $u_{ij}$ ，頂点 $i \in V$ の需要供給 $b_{i}$ が与えられたときに，需要供給を満たしつつ容量制約を満たすフローのうち，コストを最小化するものを求める問題です．数式で書くと以下のように書けます．

$\begin{align*} \begin{aligned} \min_{\boldsymbol{x} \in \mathbb{R}^{|E|}}.& && \sum_{(i, j) \in E} c_{ij} x_{ij} \\ \mathrm{s.t.}& && \sum_{j: (i, j) \in E} x_{ij} - \sum_{j: (j, i) \in E} x_{ji} = b_i \quad (\forall i \in V), \\ &&& 0 \leq x_{ij} \leq u_{ij} \quad (\forall (i, j) \in E) \\ \end{aligned} \end{align*} \tag{1}$

1つめの制約がフローが需要供給の制約を満たすことを，2つめの制約がフローが容量制約を満たすことを表現しています．

さて，この最小費用流問題は線形計画問題 (LP) の一種なので，LPとしての双対を考えることで以下の双対問題を考えることができます．

$\begin{align*} \begin{aligned} \min_{\boldsymbol{p} \in \mathbb{R}^{|V|}}. && \sum_{(i, j) \in E} u_{ij} \cdot \max(0, p_j - p_i - c_{ij}) + \sum_{i \in V} b_i p_i \\ \end{aligned} \end{align*} \tag{2}$

LP の強双対定理から，適切な条件下で主問題と双対問題の最適値は一致します．この性質を利用することで，例えばある問題が双対側の最適化問題として定式化することができるならば，双対をとって主問題に対するアルゴリズムを適用してあげることで最適値を得ることができたりするわけです．（競プロにおける双対の使い方に関しては例えば https://www.slideshare.net/wata_orz/ss-91375739 が詳しいです）

さて，最小費用流問題の双対問題，パッと見ただけでは正直なところ何をしているのかよく分からなくて覚えにくい最適化問題です．これは，最大流問題の双対問題が「頂点集合を二つに分割して分割間の辺の重みを最小化する」（つまり最小カット問題）という分かりやすい解釈を持つことと対照的です．

この記事の目的は，この分かりにくい最小費用流問題の双対問題を覚えやすい綺麗な形で書こうと頑張ることです．

最小凸費用流問題への一般化

ここで突然ですが，最小費用流問題を一般化し，以下のような問題を考えます．

$\begin{align*} \begin{aligned} \min_{\boldsymbol{x} \in \mathbb{R}^{|E|}}.& && \sum_{(i, j) \in E} \phi_{ij}(x_{ij}) \\ \mathrm{s.t.}& && \sum_{j: (i, j) \in E} x_{ij} - \sum_{j: (j, i) \in E} x_{ji} = b_i \quad (\forall i \in V). \\ \end{aligned} \end{align*} \tag{3}$

ただし， $\phi_{ij}: \mathbb{R} \to \mathbb{R} \cup \{ \pm \infty \}$ は凸関数とします．ここでの凸関数の定義は， $\phi_{ij}(x) \neq \pm \infty$ , $\phi_{ij}(y) \neq \pm \infty$ なる $x, y \in \mathbb{R}$ 及び $0 \leq t \leq 1$ なる $t$ について $t \cdot \phi_{ij}(x)+ (1-t) \cdot \phi_{ij}(y) \geq \phi_{ij}(t \cdot x + (1-t) \cdot y)$ が成立することと定義します（よくある普通の凸関数の定義を一般化したものになっています）． $\pm \infty$ に関する演算は直感的なものを採用して下さい．

この問題がもとの最小費用流問題 (1) の一般化になっていることは，

$\phi_{ij} (x_{ij}) = \left\{ \begin{array}{} c_{ij} x_{ij} & (0 \leq x_{ij} \leq u_{ij})\\ + \infty & (\mathrm{otherwise}) \end{array} \right. \tag{4}$

とするともとの問題 (1) に一致することから分かります．容量制約を破ると無限大の費用がかかるようにすることで，強制的に容量制約を守らせるようにしているわけです． $\phi_{ij}$ が凸関数であることは容易に確かめられます．

最小凸費用流問題の Fenchel 双対

さて，目的関数が非線型になり，問題が LP ではなくなってしまったため，LP の双対定理は適用する事ができません．しかし，Fenchel 双対という概念を用いることで，このような問題にも双対問題を考えることができます． Fenchel 双対は凸最適化問題に適用できる双対で，適当な仮定のもとで強双対定理なども成立します．また，LPの双対は Fenchel 双対の特殊ケースとして導出することができます． Fenchel 双対については詳しくは http://www.misojiro.t.u-tokyo.ac.jp/~murota/lect-surikeikakuhou/fenchel031129.pdf が分かりやすいです．

(3)の Fenchel 双対をとると以下のような最適化問題になります:

$\begin{align*} \begin{aligned} \max_{\boldsymbol{p} \in \mathbb{R}^{|V|}}.& && -\sum_{(i, j) \in E} \psi_{ij}(p_j - p_i) - \sum_{i \in V} b_i p_i . \end{aligned} \end{align*} \tag{5}$

あるいは最小化問題としてしまった方が綺麗かもしれません（目的関数値の符号が逆転することに注意）．

$\begin{align*} \begin{aligned} \min_{\boldsymbol{p} \in \mathbb{R}^{|V|}}.& && \sum_{(i, j) \in E} \psi_{ij}(p_j - p_i) + \sum_{i \in V} b_i p_i . \end{aligned} \end{align*} \tag{6}$

ただし， $\psi_{ij}$ は $\phi_{ij}$ の Legendre 変換です:

$\psi_{ij}(p) := \sup_{x \in \mathbb{R}} \{ p \cdot x - \phi_{ij}(x) \}. \tag{7}$

何やらややこしかったもとの双対問題 (2) に比べて，(6) はかなりすっきりとした表式になっていると思います！

主問題 (3) と双対問題 (6) の関係は，もとの最小費用流問題 (1) と双対問題 (2) の関係の一般化になっています．そのことを確認するために， $\phi_{ij}$ が式 (4) で表される場合の双対問題を考えてみましょう． Legendre 変換の定義式 (7) より，

$\begin{align*} \psi_{ij} (p) &= \sup _{x \in \mathbb{R}} \{ p \cdot x - \phi_{ij}(x)\} \\ &= \sup_{0 \leq x \leq u_{ij}} \{ p \cdot x - c_{ij} \cdot x\} \\ &= \sup_{0 \leq x \leq u_{ij}} \{ (p - c_{ij}) \cdot x\} \\ &=\left\{ \begin{array}{} u_{ij} \cdot (p-c_{ij}) & (p > c_{ij})\\ 0 & (p \leq c_{ij}) \end{array} \right. \\ &= u_{ij} \cdot \max(0, p-c_{ij}) \end{align*} \tag{8}$

なので，双対問題 (6) の $\psi_{ij}$ を (8) の式で置き換えてやれば，もとの問題の双対問題 (2) が出てきますね！

制約が変わった場合

主問題 (3) + 双対問題 (6) の形で理解しておくことのメリットとして，主問題の制約が多少変わっても双対問題が簡単に導ける点があります．

例えば，もとの最小費用流問題におけるフローの上限制約がなくなった

$\begin{align*} \begin{aligned} \min_{\boldsymbol{x} \in \mathbb{R}^{|E|}}.& && \sum_{(i, j) \in E} c_{ij} x_{ij} \\ \mathrm{s.t.}& && \sum_{j: (i, j) \in E} x_{ij} - \sum_{j: (j, i) \in E} x_{ji} = b_i \quad (\forall i \in V), \\ &&& x_{ij} \geq 0 \quad (\forall (i, j) \in E) \\ \end{aligned} \end{align*} \tag{9}$

を考えてみます．このとき

$\phi_{ij} (x_{ij}) = \left\{ \begin{array}{} c_{ij} x_{ij} & (x_{ij} \geq 0)\\ + \infty & (\mathrm{otherwise}) \end{array} \right. \tag{10}$

として $\phi_{ij}(x)$ を Legendre 変換すると，

$\begin{align*} \psi_{ij} (p) &=\left\{ \begin{array}{} + \infty & (p > c_{ij})\\ 0 & (p \leq c_{ij}) \end{array} \right. \\ \end{align*} \tag{11}$

となり，(6) と組み合わせることで双対問題を

$\begin{align*} \begin{aligned} \min_{\boldsymbol{p} \in \mathbb{R}^{|V|}}.& && \sum_{i \in V} b_i p_i \\ \mathrm{s.t.}& && p_j - p_i \leq c_{ij} \quad (\forall (i, j) \in E) \\ \end{aligned} \end{align*} \tag{12}$

と導くことができます． $p_j - p_i > c_{ij}$ の場合は目的関数が無限大になってしまい解になり得ないので，制約として $p_j - p_i \leq c_{ij}$ が入ってくる点がポイントです．

これ以外にも，制約が $l_{ij} \leq x_{ij} \leq u_{ij}$ とかになっても簡単に双対問題を求めることができます．

その他の最小費用流問題

(6) の形で双対問題が綺麗に書けたのでこの記事の目的は達せられたのですが，もう少し書きます．

$\phi_{ij}$ は凸関数なら何でもいいので，適当に凸関数を持ってくればそれに応じて最小費用流問題と双対問題ができます．凸関数をカスタマイズして自分だけの最強の最小費用流問題とその双対問題を作ろう！

例えば $\phi_{ij}(x) = \frac{1}{2} R_{ij} x^2$ （ $R_{ij}$ は適当な正実数）としてみると，Legendre 変換は $\psi_{ij}(p) = \frac{1}{2R_{ij}}p^2$ となり，主問題と双対問題は以下のようになります:

$\begin{align*} \begin{aligned} \min_{\boldsymbol{x} \in \mathbb{R}^{|E|}}.& && \sum_{(i, j) \in E} \frac{1}{2} R_{ij} x_{ij}^2 \\ \mathrm{s.t.}& && \sum_{j: (i, j) \in E} x_{ij} - \sum_{j: (j, i) \in E} x_{ji} = b_i \quad (\forall i \in V). \\ \end{aligned} \end{align*} \tag{13}$

$\begin{align*} \begin{aligned} \min_{\boldsymbol{p} \in \mathbb{R}^{|V|}}.& && \sum_{(i, j) \in E} \frac{1}{2R_{ij}}(p_j - p_i)^2 + \sum_{i \in V} b_i p_i . \end{aligned} \end{align*} \tag{14}$

この問題，なんとなく電気回路における電流と電位の関係を表現しているように解釈できそうです．各頂点 $i$ に電流 $b_i$ が流れ込んでいて，頂点 $i$ と頂点 $j$ の間に抵抗値 $R_{ij}$ の抵抗があるという電気回路を考えます．このとき，主問題 (13) は「回路全体の抵抗での発熱を最小化するような電流を求めよ」という問題になっています．これは，「最小発熱の原理」（電気回路における変分原理で，回路全体での発熱が最小の状態が現実に起こるというもの）から，実際に流れる電流を求める問題になっています．双対問題 (14) もそんな感じの解釈ができそうで，強双対定理は「電流（ $=\boldsymbol{x}$ ）で考えても電位（ $=\boldsymbol{p}$ ）で考えても実現する状態は一緒だよ」的なことを言ってそうな感じがします．

よく分からないので電気回路のことを思い出しつつちょっと考えてみます（誰か知ってたら教えて下さい）．

なんとなく思うこと

(3) と (6) の双対関係を見ていると，「フロー」（各頂点で流量の保存則が成り立つもの）と「ポテンシャル」（各辺について，両端の頂点に割り当てられている値の差が重要なもの）には本質的な双対関係があるということが感じられます．

最大流・最小カットの双対もそういう視点で見ることができます．なぜなら，最小カットは「各頂点に 0 か 1 の値を割り当てて，両端の値が異なる辺の重みの和を最小化する」問題として捉えることができて，各頂点に割り振る値がまさにポテンシャルであると解釈できるからです．最大流問題は最小費用流問題の特殊ケースとして定式化できるので，お時間がある方は実際に適当な $\phi_{ij}$ を設定して双対を取ってみると，気持ちが理解できると思います．

ここまで抽象化すると，なんとなく"世界の原理"みたいなものが垣間見えた感じがしてワクワクしますね！（厨二病）

参考文献

この辺の話は別に僕が考えたわけではなくて，昔から凸解析の分野で研究されていることです．以下の文献を見ればより詳しいことがわかると思います．

R. T. Rockafellar (1984), Network Flows and Monotropic Optimization, Wiley-Interscience.
室田一雄 (2013)，離散凸解析と最適化アルゴリズム, 朝倉書店．

私と理論

数学の話を主に書きます