I would like some hint in this homework question. I have to write the max-flow problem (with souce $s$ and sink $t$) as a linear program. I have to do this by defining variables on each $s - t$ path, which is different than the typical approach of considering as variables the flow of each edge.

So far, I thought on the following. Let $f_i$ be the flow of each $s-t$ path, then the objective would be $\max_{f_i} \sum_i f_i$, subject to every $f_i$ is less or equal that the capacity of each edge on that path, plus the flow convservation constraints on each vertex. Is this correct?


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.