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

[TaPaKaH]

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

 

[mighty2000]

Thank you for your post. It seems like you are on the right track with your solution attempt. To answer your question about edges with $c^\pi(e)=0$, you can simply set the corresponding flow values $f(e)$ to be any value between $0$ and $w(e)$. This does not affect the objective function and still satisfies the constraints, so it is a valid solution to the primal problem.

Additionally, I would suggest adding some more explanation to your solution, specifically about how you arrived at the complementary slackness conditions and how they relate to the primal and dual problems.

I hope this helps and good luck with your research!