# 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 '14 at 10:48
• If all capacities are equal to $\infty$ – Shuzheng Nov 22 '14 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 '14 at 15:08
• Write out the primal in canonical form with no capacity constraints. Take the dual and see what you get... – Nicholas Mancuso Nov 22 '14 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 ? – Shuzheng Nov 30 '14 at 19:29