- #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##.