[TOC]

最小費用流 (Minumu Cost Flow)

1. 概要

決まった量を始点から終点まで流す際にかかる費用を最小にする問題.

2. 教科書

2.1. 教科書1

Minimum cost flows Amaury Pouly, November 23, 2010

2.1.1. 概要

Minimum Cost Flow のアルゴリズム2つ及び計算量についての記述.証明も詳しいので読みやすかった.

アルゴリズムの方針(うろ覚え) 「最小費用条件」をいうものを適切に定めることで,最小費用条件を満たしているフローが最小費用流であることが示される.フロー0からスタートして重みを適切に定めたグラフ上でソースからシンクへの最短路を求めてフローを追加することで最小費用条件を常に満たされるプリフロー(容量制約のみを満たしたフローでフロー整合条件が満たされたいない)が作成できる.フローの追加作業を繰り返し行い,流したい流量まで流れた段階になったときフローであることを示すことでそれが最小費用流であることが示される.
特徴
- 枝のコストが負の場合にも対応
- 容量制約にlower bandとupper band(upper bandは $\infty$ もOK)がある場合に対応.
- 始点(surplus)、終点(demand)も複数ある場合に対応.
アルゴリズムの計算量
- アルゴリズム1 ノード数を $n$ ,枝数を $m$ の有向グラフが与えられているとする. また、各枝に対して非負の距離が定まっているとする. このとき、各枝に対してあるノード $v_{0} \in V$ からの距離を表す関数 $d : V \to R_{\geq 0}$ を求めるアルゴリズムの計算量を $f$ とする.(例えばDijkstra's algorithm with a binary heapを用いると $f = m log (n)$ らしい.) このとき,Minimum Cost Flow を求めるアルゴリズムの計算量は $O (B f)$
- アルゴリズム2 計算量がアルゴリズム1に比べて非常に大きいので略.

2.1.2. 補足

Removing nonzero lower bounds complement

Let flow ${~ f}^{*}$ is the solution of following minimum cost flow problems (1).

$\begin{matrix} min ~ f & \sum e \in A c (e) ~ f (e) subject to & \sum e \in N^{+} (v) ~ f (e) - \sum e \in N^{-} (v) ~ f (e) = b (v) - \sum e \in N^{+} (v) l (e) + \sum e \in N^{-} (v) l (e) 0 \leq ~ f (e) \leq u (e) - l (e) \end{matrix}$

Then, if we define $f^{*} \equiv {~ f}^{*} + l (e)$ , $f^{*}$ is the solution of following minimum cost flow problems (2).

$\begin{matrix} min f & \sum e \in A c (e) f (e) subject to & \sum e \in N^{+} (v) f (e) - \sum e \in N^{-} (v) f (e) = b (v) l (e) \leq f (e) \leq u (e) \end{matrix}$

(Proof) It is easy to show $f^{*}$ satisfies all the constraints of problem (1). (skip detail) Let $f$ be a flow that satisfies all the constraints of problem(2). Then, we define the $~ f$ with $f (e) = ~ f (e) + l (e)$ . Since $f$ satisfies all the constraints of problem (2), it is easy to show $~ f$ satisfies the all the constraints of problem (1). Therefore, $\begin{matrix} \sum e \in A c (e) f^{*} (e) & = \sum e \in A c (e) {~ f}^{*} - \sum e \in A c (e) l (e) \leq \sum e \in A c (e) ~ f - \sum e \in A c (e) l (e) = \sum e \in A c (e) f (e) \end{matrix}$

Lemma 2.3.1 complement

There exists $f^{\circ}$ , a minimum cost flow such that

$\begin{matrix} f^{\circ} (e_{0}) < \sum v \in V | b (v) | + \sum e \in A, u (e) < \infty u (e) (for all e_{0} \in A) \end{matrix}$

(Proof.) If we apply theorem 2.1.3 to $f^{\circ}$ : we can decompose $f^{\circ}$ into cyclic $W$ and paths $P$ .Moreover, in the proof of theorem, we properly define $f (P) (P \in W \cup P)$ such that $\begin{matrix} f^{\circ} (e_{0}) & =^f (e_{0}) \equiv \sum P \in P δ_{e_{0}} (P) f (P) + \sum W \in W δ_{e_{0}} (W) f (W) (for all e_{0} \in A) \end{matrix}$ Therefore, the objective function of minimum cost flow problem is as follows $\begin{matrix} \sum e \in A c (e) f^{\circ} (e) & = \sum p \in P {\sum e \in A δ_{e} (P) c (e)} f (P) + \sum W \in W {\sum e \in A δ_{e} (W) c (e)} f (W) = \sum P \in P c (P) f (P) + \sum W \in W c (W) f (W) \end{matrix}$ Now pick a cycle $W$ such that $f (W) > 0$ . Then we must have $c (W) \leq 0$ since $f^{\circ}$ is a minumum cost flow; otherwise we can set $f (W) = 0$ and because we have zero lower bounds, we obtain a feasible flow of strictly lesser cost than $f^{\circ}$ . Furthermore, if $c (W) = 0$ then we can set $f (W) = 0$ and obtain a feasible flow of the same cost. So we can assume that if $f (W) > 0$ then $c (W) < 0$ . But remember that $f^{\circ}$ is a minimum cost flow so if there is a cycle $W$ such that $c (W) < 0$ then at least one edge $e_{W}$ of $W$ must be saturated, that is $f^{\circ} (e_{W}) = u (e_{W}) < \infty$ otherwise we could push some more flow on W and get a better flow. Let $W^{+} = {W ∣ f (W) > 0}$ and $A W = {e_{W}, W \in W^{+}}$ . Then we have: $\begin{matrix} \sum W \in W δ_{e_{0}} (W) f (W) & \leq \sum W \in W^{+} f (W) (∵ add positive, exclude negative) = \sum e \in A W f^{\circ} (e) \leq \sum e \in A W u (e) \leq \sum e \in A, u (e) < \infty \end{matrix}$ ....(the rest of proof is same as textbook)

2.4 Removing negative costs proof

We define new problem as follows.The set of arcs is denoted by

$\begin{matrix} A^{'} & \equiv A_{+} ⊔ A_{-} = {e^{'} \in A ∣ c (e^{'}) \geq 0} ⊔ {e^{'} ∣ e^{'} = ~ e, e \in A, c (e) < 0} \end{matrix}$

, and the cost $c^{'}$ and capacity $u^{'}$ is defined as follows

$\begin{matrix} c^{'} (e^{'}) \equiv {\begin{matrix} c (e^{'}) (e^{'} \in A_{+}) - c (^{'}) (e^{'} \in A_{-}) \end{matrix} u^{'} (e^{'}) \equiv {\begin{matrix} u (e^{'}) (e^{'} \in A_{+}) u (^{'}) (e^{'} \in A_{-}) \end{matrix} \end{matrix}$

Then, the new minimum cost flow problem (1) is as follows

$\begin{matrix} min f^{'} & \sum e^{'} \in A^{'} c^{'} (e) f^{'} (e) subject to & \sum e^{'} \in N^{' +} (v) f^{'} (e^{'}) - \sum e^{'} \in N^{' -} (v) f^{'} (e^{'}) = b (v) - \sum e^{'} \in N^{' -} (v), e^{'} \in A_{-} u^{'} (e^{'}) + \sum e^{'} \in N^{' +} (v), e^{'} \in A_{-} u^{'} (e^{'}) (\forall v \in V) 0 \leq f^{'} (e^{'}) \leq u (e^{'}) (\forall e^{'} \in A^{'}) \end{matrix}$

Let flow $f^{' *}$ is the solution of this problem, and we denote the flow $f^{*}$ for the original problem as follows

$\begin{matrix} f^{*} (e) \equiv {\begin{matrix} u (e) - f^{' *} (~ e) (c (e) < 0) f^{' *} (e) (otherwise) \end{matrix} \end{matrix}$

Then, $f^{*}$ is the solution of the below problem

$\begin{matrix} min f & \sum e \in A c (e) f (e) subject to & \sum e \in N^{+} (v) f (e) - \sum e \in N^{-} (v) f (e) = b (v) 0 \leq f (e) \leq u (e) \end{matrix}$

(Proof) $\begin{matrix} \sum e \in N^{+} (v) f^{*} (e) = \sum e \in N^{+} (v), c (e) \geq 0 f^{*} (e) + \sum e \in N^{+} (v), c (e) < 0 f^{*} (e) \end{matrix}$

$\begin{matrix} \sum e \in N^{+} (v), c (e) \geq 0 f^{*} (e) = \sum e^{'} \in N^{' +} (v), e^{'} \in A_{+} f^{' *} (e^{'}) \end{matrix}$

$\begin{matrix} \sum e \in N^{+} (v), c (e) < 0 f^{*} (e) & = \sum e \in N^{+} (v), c (e) < 0 u (e) - f^{' *} (~ e) = \sum ~ e \in N^{' -} (v), ~ e \in A_{-} u (~ ~ e) - f^{' *} (~ e) = \sum e^{'} \in N^{' -} (v), e^{'} \in A_{-} u^{'} (e^{'}) - f^{' *} (e^{'}) \end{matrix}$

Therefore, $\begin{matrix} \sum e \in N^{+} (v) f^{*} (e) = \sum e^{'} \in N^{' +} (v), e^{'} \in A_{+} f^{' *} (e^{'}) + \sum e^{'} \in N^{' -} (v), e^{'} \in A_{-} u^{'} (e^{'}) - f^{' *} (e^{'}) \end{matrix}$ Similarly, $\begin{matrix} \sum e \in N^{-} (v) f^{*} (e) = \sum e^{'} \in N^{' -} (v), e^{'} \in A_{+} f^{' *} (e^{'}) + \sum e^{'} \in N^{' +} (v), e^{'} \in A_{-} u^{'} (e^{'}) - f^{' *} (e^{'}) \end{matrix}$ Therefore, $\begin{matrix} \sum e \in N^{+} (v) f^{*} (e) - \sum e \in N^{-} (v) f^{*} (e) = b (v) \end{matrix}$

Now, we conclude that $f^{*}$ satisfies all the constraints of original problem. Next, we show that $f^{*}$ makes the objective value minimum among all the flows that satisfies the constraints. The objective value for $f^{*}$ is $\begin{matrix} \sum e \in A c (e) f^{*} (e) & = \sum e \in A, c (e) \geq 0 c (e) f^{' *} (e) + \sum e \in A, c (e) < 0 c (e) (u (e) - f^{' *} (~ e)) = \sum e^{'} \in A_{+} c^{'} (e^{'}) f^{' *} (e^{'}) + \sum e^{'} \in A_{-} c (^{'}) (u (^{'}) - f^{' *} (e^{'})) = \sum e^{'} \in A^{'} c^{'} (e^{'}) f^{' *} (e^{'}) + \sum e \in A, c (e) < 0 c (e) u (e) \end{matrix}$ Now, we pick up a flow $f$ for original problem, which satisfies all the constraints, and we also define flow $f^{'}$ for new problem as follows $\begin{matrix} f^{'} (e^{'}) = {\begin{matrix} f (e^{'}) (if e^{'} \in A_{+}) u (^{'}) - f (^{'}) (if e^{'} \in A_{-}) \end{matrix} \end{matrix}$ Then, since $\begin{matrix} f (e) = {\begin{matrix} f^{'} (e) (if c (e) \geq 0) u (e) - f^{'} (~ e) (otherwise) \end{matrix} \end{matrix}$ we can show $\begin{matrix} \sum e \in A c (e) f (e) = \sum e^{'} \in A c^{'} (e^{'}) f^{'} (e^{'}) + \sum e \in A, c (e) < 0 c (e) u (e) \end{matrix}$ Moreover, since $f^{'}$ satisfies all the constraints of new problem (we show later), $\sum e \in A c (e) f^{*} (e) \leq \sum e \in A c (e) f (e)$ It shows that $f^{*}$ is the solution of original problem.

$f^{'}$ satisfies all the constraints of new problem

Proof. Since, $0 \leq f^{'} (e^{'}) \leq u^{'} (e^{'})$ (for all $e^{'} \in A^{'}$ ) is easy to show, we skip the detail. $\begin{matrix} \sum e^{'} \in N^{' +} (v) f^{'} (e^{'}) & = \sum e^{'} \in N^{' +} (v), e^{'} \in A_{+} f^{'} (e^{'}) + \sum e^{'} \in N^{' +} (v), e^{'} \in A_{-} f^{'} (e^{'}) = \sum e \in N^{+} (v), c (e) \geq 0 f (e) + \sum e \in N^{-} (v), c (e) < 0 u (e) - f (e) \end{matrix}$ Similarly $\begin{matrix} \sum e^{'} \in N^{' -} (v) f^{'} (e^{'}) & = \sum e \in N^{-} (v), c (e) \geq 0 f (e) + \sum e \in N^{+} (v), c (e) < 0 u (e) - f (e) \end{matrix}$ Therefore, $\begin{matrix} \sum e^{'} \in N^{' +} (v) f^{'} (e^{'}) - \sum e^{'} \in N^{' -} (v) f^{'} (e^{'}) & = b (v) - \sum e \in N^{+} (v), c (e) < 0 u (e) + \sum e \in N^{-} (v), c (e) < 0 u (e) = b (v) - \sum e^{'} \in N^{' -} (v), e^{'} \in A_{-} u^{'} (e^{'}) + \sum e^{'} \in N^{' +} (v), e^{'} \in A_{-} u^{'} (e^{'}) \end{matrix}$

Theorem 2.6.1 complement

We asuume that $f^{'} (e) \geq 0$ for all $e \in A_{G}$ . Then,

$\begin{matrix} \sum e \in N_{G}^{+} (v) f^{'} (e) - \sum e \in N_{G}^{-} (v) f^{'} (e) = 0 \end{matrix}$

(Proof) $\begin{matrix} \sum e \in N_{G}^{+} (v) f^{'} (e) - \sum e \in N_{G}^{-} (v) f^{'} (e) = (\sum e \in N^{+} (v) f^{'} (e) + \sum e \in N^{-} (v) f^{'} (~ e)) - (\sum e \in N^{-} (v) f^{'} (e) + \sum e \in N^{+} (v) f^{'} (~ e)) \end{matrix}$ the rest of proof is same

Lemma 2.8.3 modification MCNF

I change the assumption because the lemma is wrong. (For example, Let $e = (s, v)$ , $d (v) < c (e)$ )

Assume there is a source node $s \in V$ such that every node $v \in V$ is accessible from $s$ , Let $d$ be a potential function and $π = - d$ . Then if there is no negative cost cycle in the network, the following two conditions are equivalent: (i) $d (v)$ is the shortest path distance from $s$ to $v$ with respect to $c$ . (ii) $d (s) = 0$ and $c^{π} (e) \geq 0$ for all $e \in A$ . We add assumption that $d (v)$ is greater than or equal to the shortest path distance from $s$ to $v$ with respect to $c$ .

(Proof) (i) $\Rightarrow$ (ii) is same as the textbook. (ii) $\Rightarrow$ (i) By assumption, for all $e = (u, v) \in A$ $\begin{matrix} c^{π} (e) \geq 0 \Rightarrow c^{- d} (e) \geq 0 \Rightarrow c (e) + d (u) - d (v) \geq 0 \Rightarrow d (v) \leq d (u) + c (e) \end{matrix}$ Let $(s = v_{0}, v_{1}, \dots, v_{n} = v)$ be a path from $s$ to $v$ , $e_{i} = (v_{i - 1}, v_{i}) (i \in {1, 2, \dots, n})$ . Then, $\begin{matrix} d (v) & = d (v_{n}) \leq d (v_{n - 1}) + c (e_{n}) \leq d (v_{n - 2}) + c (e_{n - 1}) + c (e_{n}) \leq n \sum i = 1 c (e_{i}) \end{matrix}$ Since $d (v)$ is greater than or equal to the shortest path distance from $s$ to $v$ with respect to $c$ , (ii) $\Rightarrow$ (i)

Last modified by akirat1993 2019-05-26 02:56:51

Created by akirat1993 2019-05-26 02:56:51

最小費用流