The max-flow min-cut theorem states that the value of the maximum flow is equal to the minimum cut capacity.

It is possible that the max-flow and min-cut is equal to $\infty$.

However, reading Introduction to Linear Optimization by Bertsimas and Tsitsiklis, I get the impression that the max-flow and min-cut problems are dual to one another.

From duality theory, I know that, if the primal has finite optimal value then the dual has finite optimal value. Also, if the primal has unbounded optimal value, then the dual is infeasible and vice versa.

In the case of the max-flow and min-cut problems, how can they both have unbounded optimal value ??

  • $\begingroup$ "It is possible that the max-flow and min-cut is equal to ∞." -- how? $\endgroup$
    – Raphael
    Commented Nov 22, 2014 at 10:48
  • $\begingroup$ If all capacities are equal to $\infty$ $\endgroup$
    – Shuzheng
    Commented Nov 22, 2014 at 13:15
  • $\begingroup$ If you want to consider this an instance of the network flow problem, okay. Then clearly there are unbounded max-flow and min-cut. You already state that, as a consequence, the two problems can not be dual so your "impression" must be wrong. $\endgroup$
    – Raphael
    Commented Nov 22, 2014 at 15:08
  • $\begingroup$ Write out the primal in canonical form with no capacity constraints. Take the dual and see what you get... $\endgroup$ Commented Nov 22, 2014 at 18:23

1 Answer 1


Here is an example of this anomaly in linear programs:

$$ \begin{align*} & \max x & & \min \infty y \\ s.t.\; & x \leq \infty & s.t.\; & y \geq 1 \\ & x \geq 0 & & y \geq 0 \end{align*} $$

The solution to both programs is $\infty$. What goes wrong?

The duality theorem only works when all coefficients are finite. If you go through a proof of the duality theorem you'll see exactly where it fails, and this is a nice exercise.

I should also stress that $\infty$ isn't usually regarded as a legitimate number in these contexts. If we assume all coefficients are real numbers, then $\infty$ is nothing else than a type mismatch.

  • $\begingroup$ Aha ! So it goes wrong because we have entries with value $\infty$ for our linear program, but duality is valid only for linear pogram with real entries ? $\endgroup$
    – Shuzheng
    Commented Nov 30, 2014 at 19:29
  • $\begingroup$ Yes, that's the idea. $\endgroup$ Commented Dec 1, 2014 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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