次のグラフの最短距離問題のLP考えよう。
辺は(辺番号)/(辺のコスト)となっている。
LPは次のようになる。
min(y1+3(y2)+y3+3(y4)+y5)
s.t.
y1+y2=1
y1-y3-y4=0
y2+y3-y5=0
y4+y5=1
y1,y2,y3,y4,y5>=0
行列を使うと、
min{yb|y>=0, yA>=c}となる。ただし
A=
{{ 1,-1, 1,-1, 0, 0, 0, 0},
{ 1,-1, 0, 0, 1,-1, 0, 0},
{ 0, 0,-1, 1, 1,-1, 0, 0},
{ 0, 0,-1, 1, 0, 0, 1,-1},
{ 0, 0, 0, 0,-1, 1, 1,-1}}
b={1,3,1,3,1}^t
c={1,-1,0,0,0,0,1,-1}
y={y1,y2,y3,y4,y5}
y1,y2,y3,y4,y5={0, 1}の条件はいらないのかと思うが、Aは完全単模性を有しており、解が整数になることを示せる。詳しくは
http://www.misojiro.t.u-tokyo.ac.jp/~murota/lect-surikeikakuhou/integerprogunimod101222.pdf
を参照。
解が0以上の整数なので、グラフに負のループが存在しないと仮定すればyの値は確かに0または1になることがわかる。
では双対をとってみると、
max{cx|x>=0,Ax<=b}<=>
max( (x1-x2)+(x7-x8) )
s.t.
(x1-x2)+(x7-x8)<=1
(x1-x2)+(x5-x6)<=3
-(x3-x4)+(x5-x6)<=1
-(x3-x4)+(x7-x8)<=3
-(x5-x6)+(x7-x8)<=1
ここで
z1=-(x1-x2)
z2=(x3-x4)
z3=(x5-x6)
z4=(x7-x8)と置けば
max(z4-z1)
s.t.
-z1+z2<=1
-z1+z3<=3
-z2+z3<=1
-z2+z4<=3
-z3+z4<=1
s.t.以下の形はz1~z4を1~4の点としてみた時のpotentialの定義に他ならない。
なので最短距離問題は最大potential問題(?)に言い換えることが出来た。
最短距離問題を解くことによってpotentialが求められることがわかり、最小費用流のpotentialの初期化もこれで行えるようになった。
最大potential問題のことを競プロ界隈では牛ゲーという。
LPを解こうとして2変数の式が大量に出てきたときは牛ゲーを疑うと良い。
ちなみに最大フローの双対は最小カットだが、最小カットはあまり式にしてもうれしくなさそう。
集合を2つに分ける問題で使えるかも位の認識でいいと思う。
