I am learning about dual programs in a grad class, but the lectures are lacking. I had to teach myself the bounding method and I understand it, but I'm not sure how to apply it to the Max-flow problem. We did not go over how we obtained the dual in much detail during lecture.

Here is the concept I am trying to use:

To find the dual of $$\max_x c^Tx\\ \text{s.t.} Ax\leq b\\ -Ix\leq 0 $$ where $I$ is the identity matrix, note that for any $y,z \geq 0$ and feasible solution the following must hold: $$y^T(Ax-b)+z^T(-Ix)\leq 0.$$ After some manipulation, $$(A^Ty-Iz)x \leq b^Ty$$ which yields the dual $$\min_y b^Ty\\ \text{s.t.} A^Ty-Iz = c\\ y\geq 0.$$ We can then eliminate $z$ and get the constraint $A^Tx\geq c$.

From my understanding, this works because we can relate $c$ to the coefficient on $x$ in the linear combination of constraints. However, the objective function in Max-flow only deals with flow out of the source and the flow conservation and capacity constraints deal with all flows in the network. Can this method still be applied to find the dual, or is there another method I need to learn?

Here is the Max-flow problem as a LP: $$\max \sum_{v:(s,v)\in E} f(s,v)\\ \text{s.t.} \sum_{u:(u,v)\in E} f(u,v) - \sum_{w:(v,w)\in E} f(v,w) = 0, \forall v\in V - \{s,t\}\\ f(u,v)\leq c(u,v), \forall (u,v)\in E\\ f(u,v)\geq 0, \forall (u,v)\in E.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.