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?



You must log in to answer this question.

Browse other questions tagged .