Deriving the dual of the minimum cost flow problem.

Question

Assume that we have a connected digraph $G$ with node set $V$ and edge set $E$. The minimum cost flow problem is given by:

\begin{align} \min\sum&(c_{vw}x_{vw}: vw\in E)\\ &\text{subject to}\\ f_x(v)& = b_v, \forall v\in V\\ 0\leq x_{vw}& \leq u_{vw}, \forall vw\in E. \end{align}

Where,

• $x_{vw}$ is the flow on edge $vw$,
• $c_{vw}$ is the cost per unit of flow of edge $vw$,
• $f_x(v)$ is the net flow into node $v$ (or excess of $x$ at node $v$),
• $u_{vw}$ is the capacity of flow on edge $vw$,
• $b_v$ is the demand of flow on node $v$.

Apparently the dual of this minimisation problem is given by \begin{align} \max\sum(b_vy_v:v\in V) -& \sum(u_{vw}z_{vw}: vw\in E)\\ \text{subject to}&\\ -y_v + y_w - z_{vw}\leq& \,c_{vw}\forall vw\in E\\ z_{vw}\geq 0, \forall vw&\in E \end{align} by writing the constraints $x_{vw}\leq u_{vw}$ as $-x_{vw}\geq -u_{vw}$.

What I've tried:

I don't really understand why this is the dual of the minimum cost flow problem. For $Ax \leq b$ in the primal we have \begin{align} f_x(v) &=\, b_v\\ -x_{vw} &\geq -u_{vw} \end{align} That means (I'm apparently mistaken), that in the dual we would have \begin{align} \max b_v^Ty - u_{vw}^Ty \end{align} while in the correct dual the variable $z_{vw}$ is introduced. Furthermore, the constraints in the dual don't make much sense to me either. I understand that $f_x(v) = b_v$ can be written as $$\sum x_{wv} - \sum x_{vw} = b_v$$ but I'm having a hard time figuring out what this would mean for the matrix $A^T$.

Question: How should I derive the correct dual for the minimum cost flow problem?

Answer 1

If you have two kinds of constraints in a linear programming problem, in the dual you should introduce two different classes of variables. You are trying to combine these two classes of variables into one long vector, $y$. Technically, this is a correct way to do it, although you've done it wrong. If you did it the right way the objective function would be $$ \max \, [_v, -u_{vw}]^T ,$$ where $[b_v, -u_{vw}]$ is the vector composed by concatenating the two vectors $b_v$ and $-u_{vw}$.

But if you call these two classes of variables by the same name, the dual you write down will be impossible to reason about. In the original problem, you have a constraint for each vertex and a constraint for each directed edge. Thus, in the dual you get $y_v$ and $z_{vw}$.