最短経路の双対と差分制約

最短経路問題のLP双対に差分制約が出てくる理由

• 最短経路問題は最小費用流問題の、辺の容量に余裕があって1のフローを流す特殊ケースに相当する
• 辺がないことと、辺があってコストが0であることは区別しなければならない
  • 辺の有無を表現する変数を作ると複雑になる
  • ので、あらかじめ辺集合は一列に並べられて自然数と対応づけられてるとする
• それぞれの辺がどの頂点を繋いでいるのかを表現した$|E|\times |V|$ 行列Aを考える
  • i行目は、辺$i=(u,v)$についてu列=-1, v列=1としたもの
• 始点と終点を表現する$|V|$次元ベクトルbを考える
  • 始点sが-1, 終点tが1
• f: flow, c: costは$|E|$次元ベクトルとする
• こうすると線形計画問題としてシンプルに書ける
  • minimize: $f^{T}c$
  • subject to:
    • $A^{T}f=b$
    • $f\ge 0$
• 双対線形計画問題は$|V|$次元ベクトル p (potential)を使ってこう書ける
  • maximize: $p^{T}b$
  • subject to:
    • $Ap\le c$
• Aのi行目は、辺$i=(u,v)$についてu列=-1, v列=1としたもの, bは始点sが-1, 終点tが1ということを思い出すと差分の形になる
  • maximize: $p_t-p_s$
  • subject to:
    • $p_v-p_u\le c_e(\mathrm{for}\mathrm{all}e=(u,v))$

参考資料

• 双対性
• LPとグラフと定式化
• どちらも点に出入りする辺の集合${\delta }^{+}(v),{\delta }^{-}(v)$を使って定式化しているが、それが行列の掛け算で表現された線形計画問題の一般形にどう対応するのかと、どう双対になるのかが僕にとっては自明ではなかったので噛み砕いた。