双対問題

接続行列\(A\in\mathbb{R}^{|V| \times |E|}\)と置く。最小費用流問題は線形計画問題として定式化すると、\begin{equation*}
\begin{array}{ll@{}ll}
\text{min} & cx &\\
\text{subject to}&\overline b \geq Ax \geq \underline b\\
& \overline u \geq x \geq \underline u
\end{array}
\end{equation*}となる。この値を下から評価してみる。

卸業者 A : 辺 \(e\) をコスト \(c_e\) で通れる。各頂点の需給を満たすように輸送したい。転売屋 B : 頂点 \(i\) で物価（ポテンシャル、価格関数） \(\pi_i\) で売買して需給を満たしたい。B は関税が掛からない。B は在庫と資金が無限にあるので買った量と売った量は一致しなくてもよい。 B は A の輸送費（主問題の答え）以下の総費用を提示したい。

\(\partial x_v = b_v\) のとき、頂点 \(v\) での売買に掛かる費用は \(\pi_vb_v\) である。B は \(\min(\pi_v \overline b_v , \pi_v \underline b_v)\) を費用に加える。

B が頂点 \(u\) で買い頂点 \(v\) で売るための費用は \(\pi_u-\pi_v\) である。従って、A は辺 \(e=(u, v)\) の単位流量当たり、少なくとも \(c_e^\pi = c_e-(\pi_u-\pi_v)\) だけ B より費用が大きい。従って、B は \(\min(c_e^\pi \overline u_e, c_e^\pi \underline u_e)\) を費用に加える。\(c_e^\pi\) を簡約費用と呼ぶ。

B はできるだけ高い額を提示したいので、
$$\mathrm{max} \quad \sum_v \min \left(\pi_v \overline b_v , \pi_v \underline b_v\right)+\sum_e\min\left(c_e^\pi \overline u_e, c_e^\pi \underline u_e\right)$$である。この値が主問題の下からの評価になっていること（弱双対性）は作り方から明らかである。更に、主問題と値が等しいことが強双対性定理で言える。次のような解釈もある。フローをパスとサイクルに分解する。流量１のs-tパスの簡約費用の和は (パスの費用)\(-\pi_s+\pi_t\) となる。また、流量１のサイクルの簡約費用の和は（パスの費用）となる。ここから、双対問題が主問題のlower boundであることは明らか。超頂点を追加してｂフロー（\(\partial x = b\) の場合）に帰着すると、最小費用流であることと、残余ネットワークに負閉路が存在しないことが同値。負閉路が存在しないので最短距離が定義でき、最短距離から簡約費用が非負になるポテンシャルが取れる。残余ネットワーク上に簡約費用負の辺がないことから、以下が成り立つ。相補性条件を使ってもよい。

• \(x_e = \underline u_e\) ならば \(0 \leq c_e^\pi\)
• \(\underline u_e < x_e < \overline u_e\) ならば \(c_e^\pi=0\)
• \(x_e = \overline u_e\) ならば \(c_e^\pi \leq 0\)

が成り立つ。目的関数は$$\mathrm{max} \quad \sum_v \pi_v b_v +\sum_e\min\left(c_e^\pi \overline u_e, c_e^\pi \underline u_e\right)$$の形なので、（主問題の答え）＝（双対問題の答え）となる。
先の目的関数を線形計画問題として定式化するには、min を消去する必要がある。そこで \(\pi = \pi^++\pi^-, c^\pi=c^{\pi+}+c^{\pi-}\) という変数変換をして、\begin{equation*}
\begin{array}{ll@{}ll}
\text{max} & \overline b \pi^-+\underline b \pi^+ +\overline u c^{\pi-} +\underline uc^{\pi+} &\\
\text{subject to}& c^{\pi+} + c^{\pi-} = c-A^T (\pi^-+\pi^+)\\
& c^{\pi-} \leq 0 \\
& c^{\pi+}\geq 0 \\
& \pi^- \leq 0 \\
& \pi^+ \geq 0 \\
\end{array}
\end{equation*} となる。この変換で最適解は変化しない。

頂点 \(v\) に出る辺しか存在せず \(\underline b_v = 0\) である場合

\(\pi_v \geq 0\) において \(\min \left(\pi_v \overline b_v , \pi_v \underline b_v\right)=0\), \(v\) から出る辺 \(e\) について \(\sum_e\min\left(c_e^\pi \overline u_e, c_e^\pi \underline u_e\right)\) は \(\pi_v\) について単調減少だから、最適解では \(\pi_v \leq 0\) である。これは、\(\pi_v \geq 0\) ならば頂点 \(v\) で買い物をしない選択肢 \(\partial x_v = 0\) を取ることができ、このとき、A との価格差が最も開くのが \(\pi_v = 0\) であることからきている。

頂点 \(v\) に入る辺しか存在せず、\(\overline b_v = 0\) である場合

同様にして \(\pi_v \geq 0\) となる。

\(\overline b_v = \infty\) である場合

\(\underline u_{uv} \leq x_{uv} < \infty\) とすると \(\min(c_{ab}^\pi \cdot \infty, c_{uv}^\pi \underline u_{uv})\) を最大化するには \(c_{uv}^\pi \geq 0\) とする必要があり \(\pi_u \leq \pi_v+c_{uv}\) で差分制約が作れる。\(\pi_v < 0\) だと B は \(v\) で買うことで無限にコストを下げられてしまう。\(\underline b_v = -\infty, \overline b_v = \infty\) とすると \(\pi_v = 0\). 従って、\(\pi_u \geq A\) というような形の制約が差分形式の制約と合わせると作れる。

\(\overline u_e = \infty\) である場合

\(c_e^\pi \geq 0\) である。

二部グラフの重み付きマッチング

Egerváryの定理（AtC）：
二部グラフ\(G=(V,E)\)に対して \(\min_{u:V \to \mathbb{R}_+} \sum_{i\in V}u_i\) s.t. \(u_i+u_j \geq c_{ij}\) for all \(ij \in E\) は \(\max_{w:E\to\mathbb{R}_+} \sum_{e \in E} w_ec_e\) s.t. \(\sum_{i \in e} w_e \leq 1\) for all \(i \in V\) と等しい。(vertex cover) ≥ (matching) は明らか。等号 \(u_i+u_j=c_{ij}\) が成り立つ辺 \(ij\) の集合 \(F\) および \(u_i > 0\) となる頂点 \(i\) の集合 \(U\) を取る。\(U\) を覆う \(F\) の部分集合からなるマッチングが取れる。さもなくば、結婚定理より\(|S|>|N(S)|\) を満たす独立集合 \(S \subseteq U\) が取れて、\(S\) の頂点の重みを \(\varepsilon\) 減少, \(N(S)\) の頂点の重みを \(\varepsilon\) 増加させると解を改善できる□ \(\min_{u:V \to \mathbb{R}_+} \sum_{i\in V}a_iu_i\) の場合は、頂点 \(i\) を \(a_i\) 個に複製すると同様に処理できる。
最小費用流問題の主問題・双対問題として理解することもできる。
二部グラフの重み付きマッチングの符号を反転した問題の双対が、
\begin{equation*}
\begin{array}{ll@{}ll}
\text{max} & \sum_{v \in S} \pi_v^- -\sum_{v \in T} \pi_v^+ &\\
\text{subject to}& c^{\pi+} = c-A^T (\pi^-,\pi^+)^T\\
& \pi^- \leq 0 \\
& \pi^+ \geq 0 \\
& c^{\pi+} \geq 0 \\
\end{array}
\end{equation*}のように書ける。二部グラフの最小頂点被覆と捉えられる。ただし、部集合 \((S, T)\) 、辺 \(e\) の重み \(-c_e\) としている。逆全域木問題やABC224Hがこれに帰着される。

例題

行列 \(a\) と数列 \(b, c\) が与えられる。
\begin{align}
&\max_x\left(\sum_{i,j}a_{i,j}|x_i-x_j| +\sum_i c_i|x_i-c_i| \right)\\
=&\max_y\left(\sum_{i,j}a_{i,j}|c_i-c_j+y_i-y_j| +\sum_i c_i|y_i|\right)\\
=&\max_y\left(\sum_{i,j}\min(a_{i,j}\left(c_i-c_j+y_i-y_j\right),-a_{i,j}(c_i-c_j+y_i-y_j)) +\sum_i \min(c_iy_i,-c_iy_i)\right)\\
\end{align}（ICPC2020NERC O）

\begin{align}
&\begin{array}{ll@{}ll}
\text{max} & \sum_{e \in E} y_e &\\
\text{subject to}
& x_n-x_1 \leq D \\
& x_b \geq x_a + c_{ab} + y_{ab} & \text{for $ab \in E$}\\
\end{array}\\
=&\begin{array}{ll@{}ll}
\text{max} & \sum_{ab \in E} \min(\infty(-c_{ab}-x_a+x_b), 1(-c_{ab}-x_a+x_b)) + \min(\infty(D+x_1-x_n), 0)&\\
\end{array}
\end{align}つまり、いくつかの1-Nパス \(P_1, P_2, \ldots, P_k\) で辺を全て覆ったときの \(\sum_i (D-c(P_i))\) の最小値が答え。

\begin{align}
&\begin{array}{ll@{}ll}
\text{min} & \sum_{uv \in E} |x_v-x_u| &\\
\text{s.t.}
& \sum_{v\in V} |x_v-A-v| \leq K \\
\end{array}\\
=& \text{max}_{\lambda\geq0} \min \sum_{uv \in E} |x_v-x_u|-\lambda(K-\sum_{v\in V} |x_v-A-v|)\\
=& \text{max}_{\lambda\geq0}-\lambda K – \max \left( \sum_{uv \in E} \min(x_v-x_u,-(x_v-x_u))+\lambda \sum_{v\in V} \min(A_v-x_v, -(A_v-x_v)) \right)\\
\end{align}

ラグランジュ緩和を使用。隣接する頂点 \(u, v\) 間に容量1の辺を双方向に, 頂点vから超頂点sに容量\(\lambda\), コスト\(A_v\)の辺, 超頂点sから超頂点vに容量\(\lambda\), コスト\(-A_v\)の辺(AtC)。

\begin{align}
&\begin{array}{ll@{}ll}
\text{min} & \sum_{i,j} c_{ij}|x_i-x_j|+\sum_id_ix_i &\\
\text{s.t.}
& \sum x_i \geq H \\
& x_i \geq 0
\end{array}\\
=& \text{max}_{\lambda\geq0} \min \sum_{i,j} c_{ij}|x_i-x_j|+\sum_i d_ix_i-\lambda(-H+\sum_{i} x_i)\\
&\text{s.t.} \ \ x_i \geq 0\\
=& \text{max}_{\lambda\geq0} \lambda H- \max \left(\sum_{i,j} c_{ij}\min(x_i-x_j,-(x_i-x_j))+\sum_{i} (\lambda-d_i)x_i + \sum_i \min(0, \infty x_i)\right)\\
\end{align}
辺のコストが0なので需給を満たす循環流の存在を最大流で判定。
残余ネットワーク上で非自明な有向カット\(E(V \setminus A, A)\)を取り\(A\)の頂点に定数倍足すことで\(\sum x_i \geq H\)を満たすようにするJAG