1
$\begingroup$

Consider the standard max-flow problem with some capacity constraints in the network, and a constraint that limits the total outflow to be 1.

If one considers the dual problem, it turns out to be the min-cut problem.

Consider instead of finding the complete dual, only dualizing the capacity constraints, obtaining a relaxation in the process that depends on the dual variables.

Now for each choice of dual variables, the relaxed problem seems to be a shortest-path problem. However if there was no duality gap, that should mean that the original flow problem should have a single-path solution. This doesn't seem to be the case. Therefore it seems that dualizing only some of the constraints results in a duality gap.

Perhaps the above reasoning has some error. More generally, is it true that zero duality holds in LPs, when one only dualizes some of the constraints?

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .