2
$\begingroup$

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

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

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.

$\endgroup$
  • $\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 Nov 30 '14 at 19:29
  • $\begingroup$ Yes, that's the idea. $\endgroup$ – Yuval Filmus Dec 1 '14 at 0:07

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.