1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You can show what you think is the correct dual? $\endgroup$ – LinAlg Apr 11 '18 at 14:54
  • $\begingroup$ @LinAlg Well I'm not able to show that it is correct, but in the book "Combinatorial Optimization" by Cook this is given as the dual of the minimum cost problem yes! $\endgroup$ – titusAdam Apr 11 '18 at 15:27
  • $\begingroup$ I was wondering if you could derive the dual problem. Then I can show it is correct and equivalent to the given dual. $\endgroup$ – LinAlg Apr 11 '18 at 15:28
  • $\begingroup$ @LinAlg Ah I see. I'll try! $\endgroup$ – titusAdam Apr 11 '18 at 15:41
  • 1
    $\begingroup$ the dual function you report does not make sense. Which is the dimension of the dual vector $y$? Is it $|V|$ or $|E|$? Consider that’s in the primal you have two set of constraints: a constraint for each node $v$ and a constraint for each edge $(v,w)$. Thus in the dual you have a variable for each node ($y_v$) and a variable for each edge ($z_{vw}$). $\endgroup$ – Marcello Sammarra Apr 14 '18 at 18:24
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.