• Support PF! Buy your school textbooks, materials and every day products Here!

Using dual solution and max flow algorithm to find min cost flow

  • Thread starter TaPaKaH
  • Start date
  • #1
54
0

Homework Statement


For directed graph ##G=(V,E)## with edge capacities ##w:E\to\mathbb{R}^+##, edge costs ##c:E\to\mathbb{R}^+## and node balances ##b:V\to\mathbb{R}##, let
$$\begin{array}{llr}\max & \sum_{e\in V}c(e)f(e) \\ \text{s.t.} & \sum_{(u,v)\in E}f(u,v)-\sum_{(v,u)\in E}f(v,u)=b(u) & \text{for all }u\in V \\ & 0\leq f(e)\leq w(e) & \text{for all }e\in E\end{array}$$ be the min.cost flow problem with dual
$$\begin{array}{llr}\max & \sum_{u\in V}b(u)\pi(u)-\sum_{e\in E}w(e)a(e) \\ \text{s.t.} & \pi(u)-\pi(v)-a(u,v)\leq c(u,v) & \text{for all }(u,v)\in E \\ & a(e)\geq0 & \text{for all }e\in E.\end{array}$$
Given solution of the dual problem, obtain the min cost flow ##f## to primal by solving the max flow problem.

3. Attempt at a solution.
Let ##\pi##, ##a## be dual optimal values.
For reduced costs ##c^\pi:E\to\mathbb{R}## defined as ##c^\pi(u,v)=c(u,v)+\pi(v)-\pi(u)## we have ##a(e)=\max\{0,-c^\pi(e)\}## so by complementary slackness
$$\begin{cases}f(e)(c^\pi(e)+a(e))=0\\a(e)(w(e)-f(e))=0\end{cases}\quad\text{for all }e\in E$$we get
##c^\pi(e)<0 \Rightarrow f(e)=w(e)##
##c^\pi(e)>0 \Rightarrow f(e)=0##.
I guess I have to figure out what to with edges, for which ##c^\pi(e)=0## but I can't see any modification of ##G## such that solving max flow on it will yield a min cost flow on ##G##.
 

Answers and Replies

Related Threads on Using dual solution and max flow algorithm to find min cost flow

  • Last Post
Replies
0
Views
4K
Replies
6
Views
955
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
6
Views
4K
Replies
3
Views
2K
  • Last Post
Replies
0
Views
4K
Replies
8
Views
885
  • Last Post
Replies
1
Views
3K
Replies
1
Views
439
Replies
2
Views
2K
Top