Mininum Cost Flow, Part1: Key Concepts

元記事:http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow1
がんばって訳してみるテスト。図は載せてないので原文を参照してね。

この記事はいわゆる「最小費用流」と呼ばれる問題をカバーする。この問題はTopCoderの参加者とプロフェッショナルプログラマの両方に沢山の応用を持っている。この記事はこの話題に詳しくない読者を対象としており、重厚な理論や技術的な詳細よりも関連する考え方の概要を理解することに焦点を当てる。(前文以下略)

Statement of the Problem

最小費用流とは何だろう？重要な技術用語から始めよう。

$G=(V,E)$ を頂点の集合Vと辺の集合Eで定義される有向ネットワークとする。各辺 $(i,j) \in E$ に対して、その辺を流れうる最大量を容量 $u_{i,j}$ と定義する。各辺 $(i,j) \in E$ に対して、単位流毎のコストをコスト $c_{i,j}$ と定義する。

各頂点 $i \in V$ に対して、 $b_i$ を定義する。この値はその頂点の需要/供給を表している。もし、 $b_i > 0$ なら、ノード $i$ は供給点(supply node)と言う。もし、 $b_i < 0$ なら、ノード $i$ は需要点(demand node)と言う。(その需要は $-b_i$ と等しい) もし、 $b_i = 0$ なら、ノード $i$ は積み替え点(transshipment)と言う。

簡単のため、Gを輸送ネットワークと呼び、全てのネットワークパラメータを明示したいときは $G=(V,E,u,c,b)$ と書く。

辺 $(i,j) \in E$ のフローを $x_{ij}$ で表現する。最小費用流問題の最適化モデルをつぎのように表現できる。

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

ただし

$\begin{array}{cc} \sum_{\{j:(i,j) \in E\}} x_{ij} - \sum_{\{j:(j,i) \in E\}} x_{ji} = b_i & {\rm for all} i \in V \\ 0 \leq x_{ij} \leq u_{ij} & {\rm for all} (i, j) \in E \end{array}$

(訳注:数式汚いな…)

最初の制約条件は、(ノードから出てくるフローの合計)-(ノードに入るフローの合計)がこのノードの mass balance (供給需要値)に等しくなければならないことを述べたものだ。これは mass balance constraints として知られている。次に、flow bound constraintsはフローの範囲に課せられる物理的容量や制限を定式化したものだ。ご覧の通り、この最適化モデルは、例えば、1種類の商品しか扱っていないときの倉庫と商店の間の典型的関係を表している。我々は倉庫のサブセットから商品を各商店へ輸送するとき、輸送にかかる費用を最小化したい。

この問題はSimplex法を使うことで解くことができるが、この記事では、ネットワーク流理論に関係する他のアイデアに焦点を当ててみる。最小費用流問題を解くのに使う3つの基本的なアルゴリズムに進む前に、必要とされる理論的基礎を復習しよう。

Finding a solution

いつ、最小費用流問題は有効な(必ずしも最適でなくてもよい)解を持つのだろうか？どうやったら商品を輸送できるかどうかを決定できるのだろうか？

もし、 $\delta := \sum_{i \in V} b_i \neq 0$ ならば、その問題は解を持たない。なぜならば、需要か供給のどちらかがネットワークを占め、mass balance constraints が作用する。(訳注: 訳が微妙。原文は because either the supply or the demand dominates in the network and the mass balance constraints come into play.)

しかし、供給需要値 $b_r = -\delta$ を持つ特別なノード $r$ を追加することによってこの状況を簡単に回避できる。今、私たちには2つの選択肢がある：もし、 $\delta > 0$ (供給過多)ならば、 $b_i > 0$ であるノード $i \in V$ に対して、無限のキャパシティとゼロのコストを持つ辺 $(i,r)$ を追加する。そうでないときは(需要過多)、 $b_i < 0$ であるノード $i \in V$ に対して、上と同様な辺 $(r,i)$ を追加する。こうして、 $\sum_{i \in V \cup \{r\}} b_i = 0$ である新しいネットワークが構築できた。そして、このネットワークは目的の関数と同じ最適解を持つことが簡単に証明できる。

頂点rをゴミやクズの山だと思おう。もし、商店が倉庫の供給量よりも多くのものを要求するなら、ゴミのような役に立たない商品を取り出さなければならない。そうでなければ、私たちはゴミ山から欠けている商品を取る。これは現実世界ではいかがわしいが、もちろん、私たちの目的に対しては、このことはとても便利である。注意すべきことは、この場合、(ゴミと一緒に)集められた問題の"解"が厳密に何であるかを言うことはできないということである。さらに、"ゴミ"を使用する緊急事態をどうやって分類するかは読者に任せられている。例えば、商店の要求や倉庫に残った商品は、unsatisfiedなままにしておくこともできる。

もし、 $\delta = 0$ であったときでさえ、辺の容量によっては供給点から需要点まで十分なフローを輸送できないかもしれない。ネットワークが適するフローを持つかどうかを決定するために、問題の制約条件を満たす輸送路を見つけたい。もちろん、有効な解は必ずしも最適解ではない。しかし、もしそれが存在しなければ、問題を解くことはできない。

source node s 及び sink node t を導入しよう。 $b_i > 0$ であるノード $i \in V$ に対して、G に容量 $b_i$ とコスト0を持つ source arc $(s,i)$ を追加する。 $b_i < 0$ であるノード $i \in V$ に対して、G に容量 $-b_i$ とコスト0を持つ sink arc $(i,t)$ を追加する。

新しいネットワークは transformed network と呼ばれる。次に、s から t への最大流問題を解く(コストは無視する, fig.2を参照)。もし、最大流がsource arcs及びsink arcsをすべて飽和させたならば、その問題は有効な解を持つ。そうでなければ、その問題は有効な解を持たない。どうしてこのアプローチがうまくいくのかに関しては、証明を読者に任せることにする。

最大流を見つけたら、source arcs, sink arcs及びすべての隣接する辺を除去して、G の適したフローを手に入れることが出来る。では、どうやって、フローが最適化どうかを判定するのだろうか？このフローは目的関数zのコストを最小化するのだろうか？これらの質問に答えるために、普通、"最適化条件"を検証するのだが、それをするのはちょっと待って、いくつかの仮定について議論をしよう。

(つづく)