Mininum Cost Flow, Part1: Key ConceptsComments (2)

仮定

一般性を失うことにもつながりうるが、ネットワーク流理論の基礎を理解するうえで、いくつかの仮定を置くことは役に立つ。もちろん、これらの仮定を用いなくとも問題を解くことはできるが、解法はあまりに複雑になる。幸運なことに、これらの仮定は見た目ほどきついものではない。

仮定1. すべてのデータ $(u_{ij}, c_{ij}, b_i)$ は整数である。

コンピュータを使って処理する必要があるので、この仮定は実際には厳しいものではない。適当な大きい数を掛けることによって有理数を整数に変換できる。

仮定2. ネットワークは有向である

もし、ネットワークが無向なら、有向なネットワークに変換できる。不幸なことに、この変換は辺のコストが負でないことを要求する。この仮定をvalidateしよう。

無向なケースを有向なケースに変換するために、iとjを結ぶ無向な辺を二つの有向な辺(i, j)と(j, i)で置き換える。その容量とコストは置き換えられた辺と同じである。この
変換の正しさを言うために、まず、無向な辺 $(i, j) \in E$ が制約 $x_{ij} + x_{ji} \leq u_{ij}$ を持ち、目的関数に項 $c_{ij}x_{ij} + c_{ji}_x{ji}$ を持つことに注目する。 $c_{ij} \geq 0$ が与えられたとき、最適な解では、 $x_{ij}$ と $x_{ji}$ のどちらかがゼロになる。このよな解をnon-overlappingと言う。元のネットワークの全てのnon-overlappingなフローが同じコストを持つ変換されたネットワークに関連するフローをもつことは簡単に確認できる。逆もまた真である。

仮定3. 全ての辺のコストは非負である。

この仮定は一般性を欠くことを暗示する。もし、負のコストを持つネットワークが負の閉路を持たないならば、負のコストを持たないネットワークに変換できるとこを後で示す。しかしながら、これから議論するアルゴリズムのひとつ(cycle-canceling algorithm)は、この仮定なしでも動作させることが可能である。

各頂点 $i \in V$ に対して、ノードiのポテンシャル $\pi_i$ を関連付ける。次に辺 $(i, j) \in E$ の還元されたコスト $c_{ij}^{\pi}$ を

$c_{ij}^{\pi} = c_{ij} + \pi_i - \pi_j$

で定義する。目的関数はどのように変わるだろうか。還元された値を $z(x,\pi)$ と表す。明らかに、もし $\pi = 0$ なら、

$z(x, 0) = \sum_{(i,j) \in E} c_{ij} x_{ij} = z(x)$

である。その他の $\pi$ の値に対しては、次のような結果になる。

$z(x,\pi) = \sum_{(i,j) \in E} c_{ij}^{\pi} x_{ij} = z(x) + \sum_{(i, j) \in V} \pi_i b_i$
(訳注:めんどいので途中式省略しました)

$\pi$ を固定すると、差 $z(x,\pi) - z(x)$ は定数になる。それゆえに、 $z(x,\pi)$ を最小化するフローは、 $z(x)$ を最小化する。逆もまた成り立つ。

定理1

任意のノードのポテンシャル $\pi$ に対して、 $c_{ij}$ のコストを持つ最小費用流問題と $c_{ij}^{\pi}$ のコストを持つ最小費用流問題は同じ最適解を持つ。さらに

$z(x, \pi) = z(x) + \sum_{i \in V} \pi_i b_i$

次の結果は還元されたコストに関するとても有用な性質を含んでいる。

定理2

Gを輸送ネットワークとする。Pを $a \in V$ から $b \in V$ へ有向な経路だとする。任意のノードのポテンシャル $\pi$ に対して

$\sum_{(i,j) \in P} c_{ij}^{\pi} = \sum_{(i,j) \in P} c_{ij} + \pi_a - \pi_b$

Wを有向な閉路とする。任意のノードのポテンシャル $\pi$ に対して

$\sum_{(i,j) \in P} c_{ij}^{\pi} = \sum_{(i,j) \in P} c_{ij}$

この定理は次の論拠を示している。頂点sを導入し、各ノード $i \in V$ に対して正の容量とゼロのコストを持つ辺(s,i)をGに導入しよう。各 $i \in V$ に対して、数 $\pi_i$ がコスト関数cに関して、sからiまでの最短経路の長さを表すとする。(Reminder: 負の閉路は存在しない) もし、そうなら、各 $(i, j) \in E$ に対して、最短経路の最適性条件が満たされることを確認できる:

$\pi_j \leq \pi_i + c_{ij}$

なぜならば、 $c_{ij}^{\pi} = c_{ij} + \pi_i - \pi_j$ および $0 \leq \pi_i - \pi_j + c_{ij}$ より $c_{ij}^{\pi} \geq 0$ なので。さらに、定理2を適用することで、もしGが負の閉路を含むならば、還元されたネットワーク上では任意のポテンシャル $\pi$ に対して、それは負になる。だから、もし、輸送ネットワークが負の閉路を持たないなら、導入された頂点sに対して、最短経路を探すことで、コストを還元して、コストを正にすることができる。そうでないなら、仮定は成り立たない。もし、読者が、どうやって負のコストを持つグラフから最短経路を探すのか知らないならば、グラフ理論の基礎に戻ろう。この目的を達成するために、Bellman-Ford アルゴリズムを使うことができる。

このコスト還元テクニックはいろいろな応用や他のアルゴリズム(例えば、疎なネットワークにおける全ての最短経路の組を見つけるJohnsonのアルゴリズム)で現れるので、このテクニックをよく覚えておこう。

仮定4. 頂点の供給/需要は条件 $\sum_{i \in V} b_i = 0$ を満たし、最小費用流問題は有効な解を持つ。

この仮定はこの記事の"Find a Solution"セクションの帰結である。もし、ネットワークがこの仮定の最初の部分を満たさないなら、問題は解を持たないか、そのセクションで概略を述べているステップに従って対応する変換を作ることができる。もし、仮定の二番目の部分が成り立たないなら解は存在しない。

実のところ、これらの仮定を置くことによって、元の輸送ネットワークを変換することができるのだが、多くの問題は、しばしば全ての仮定を満たした方法で与えられる。

全ての準備がこれで終わったので、Part2でアルゴリズムの議論を始めよう。

References

[1] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications.
[2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. Introduction to Algorithms.
[3] _efer_. Algorithm Tutorial: Maximum Flow.
[4] gladius. Algorithm Tutorial: Introduction to graphs and their data structures: Section 3.References

仮定

仮定1. すべてのデータは整数である。

仮定2. ネットワークは有向である

仮定3. 全ての辺のコストは非負である。

定理1

定理2

仮定4. 頂点の供給/需要は条件を満たし、最小費用流問題は有効な解を持つ。

References

仮定1. すべてのデータ $(u_{ij}, c_{ij}, b_i)$ は整数である。

仮定4. 頂点の供給/需要は条件 $\sum_{i \in V} b_i = 0$ を満たし、最小費用流問題は有効な解を持つ。