Reputation: 1
I'm working on a flow network where all edge capacities are known constants except for two edges, e1 and e2. The capacities of these edges, c1 and c2, are non-negative variables satisfying the constraint c1 + c2 ≤ K, with K being a given positive number.
I need to compute the maximum possible flow from the source s to the sink t by optimally choosing c1 and c2 under these constraints.
My Question:
What is an efficient algorithm or method to find this maximum flow? How can I determine the optimal values of c1 and c2 that achieve this flow? Any suggestions or insights would be greatly appreciated!
I thought about formulating the problem as a Linear Programming (LP) problem since c1 and c2 are variables with linear constraints, and the flow through the network depends on their values.
Another idea was to analyze the network's cuts to see how they involve e1 and e2. By understanding how these edges contribute to the bottlenecks in the network, I might be able to express the maximum flow as a function of c1 and c2, and then optimize accordingly within the given constraints.
Upvotes: 0
Views: 32