# How can the max-flow and min-cut problems, if dual to one another, both have unbounded optimal value?

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 ??

• "It is possible that the max-flow and min-cut is equal to ∞." -- how?
– Raphael
Nov 22, 2014 at 10:48
• If all capacities are equal to $\infty$ Nov 22, 2014 at 13:15
• 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.
– Raphael
Nov 22, 2014 at 15:08
• Write out the primal in canonical form with no capacity constraints. Take the dual and see what you get... Nov 22, 2014 at 18:23

\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?
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.
• 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 ? Nov 30, 2014 at 19:29