最大フロー問題（循環フロー問題）の双対をとる

はじめに

近似アルゴリズム(V.V.ヴァジラーニ)の12章に最大フロー問題とその双対問題が載っているのだが、どのように変形したらその双対問題の式が得られるのか結構悩んだ。
そこで、未来の自分のために最大フロー問題から双対問題を導出する過程をまとめておく。

最大フロー問題と双対問題

最大フロー問題についてはリンク最大フロー問題 - Wikipediaを参照。

まず、近似アルゴリズム(V.V.ヴァジラーニ)では下記のように定式化されている。
一般的な最大フロー問題に、 $t$ から始点 $s$ へ容量が無限大の仮想的な辺を加え、循環フロー問題として考えている。
そうすることで、 $s$ でもフロー保存則が成り立つ．また、このとき目的関数では、仮想的な辺を流れるフロー $f_{ts}$ を最大にすることになる．

f:id:utsubo_21:20180518230556p:plain:w600

制約式の意味は

辺を流れるフロー量が容量を超えない。
フロー保存則（頂点に入ってくるフロー量より出ていく量の方が大きい）

これの双対を取ると下式になるとのこと。

f:id:utsubo_21:20180518230853p:plain:w600

実際に主問題を式変形をして、双対問題を得てみる。

双対をとる

まず、双対問題とは主(最大化)問題の上界を求める問題といえる（詳しくは後述）。
主問題の制約式の１つ目の両辺に $d_{ij}$ 、2つ目の両辺に $p_i$ を掛ける。

f:id:utsubo_21:20180518231614p:plain:w600

(3a)と(3b)の和は、 $d_{ij}$ 、 $p_i$ の設定によっては、主問題の上界となる。
この上界を $d_{ij}$ 、 $p_i$ を上手く設定して最小化するのが、双対問題である。
(4) = (3a) + (3b)

f:id:utsubo_21:20180520120544p:plain:w600

上式が上界になる条件は「(4)左辺の $f_{ij}$ の係数の和が、主問題の目的関数の $f_{ij}$ の係数より大きい」であり、これが双対問題の制約式となる。

(4)(=(3a)+(3b))の左辺の $f_{i,j}$ の係数について考える。

(3a)で $f_{ij}$ は、 $d_{ij}f_{ij}$ がある。

(3b)では、頂点 $i$ と頂点 $j$ についての不等式で必ず現れる（元はフロー保存則を表す式なので）。
頂点 $j$ には、フロー $f_{ij}$ が流れこむはずなので、 $p_j f_{ij}$ が必ず存在し、
頂点 $i$ には、フロー $f_{ij}$ が出ていくはずなので、 $-p_i f_{ij}$ がある。