0
$\begingroup$

enter image description here

enter image description here

enter image description here

So this is the maximum flow problem and I have two questions here:

  1. Why do we write maximize X_jt and why not X_st, since we want to maximize the flow from the source node to the end node? And why do we write X_jt if we do
  2. For the constraints what does X_jl mean? Why l there?
$\endgroup$

1 Answer 1

3
$\begingroup$
  1. In the graph, we didn't have the direct connection between source and sink. However, we can reach sink from source by pass intermediate nodes. Therefore, we maximum all of arc's flow. Or you can just maximize the out-going flow from the source. Because the flow conservation constraints would ensure the all flow from source would going to sink finally.

  2. In this problem, we have flow conservation constraints, which means the flow between nodes would be the same (except source and sink). To formulate this, you can imagine each index as following i : in-coming nodes, j : current node, l : out-going nodes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.