maxflow - Proportionality constraint for multiple sources
I am investigating using maxflow to calculate the max flow from multiple sources based upon network constraints. Is there a way to insure that all nodes upstream of a constraint are reduced proportionately instead of having the constraint being honored by reducing the flow on just the minimum number of nodes needed to meet the constraint value. Consider the following directed graph: <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/file/n4025881/Network-01.png> When I calculate the maxflow with the attached program gt-test001.py <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/file/n4025881/gt-test001.py> , I receive the following results (minus the super nodes and reformatted for clarity). max flow = 39.0 E6 = 8.0 E7 = 8.0 E8 = 11.0 E9 = 12.0 E10 = 16.0 E11 = 21.0 E12 = 39.0 However, the treatment that I am looking for results in: max flow = 39.0 E6 = 7.53 E7 = 8.47 E8 = 11.0 E9 = 12.0 E10 = 16.0 E11 = 21.0 E12 = 39.0 In this case V1 and V2 can deliver 17 but is restricted to 16 by E10 on the outbound side of V3. I want to reduce V1 & V2 proportionately to their capacity such that E6 = (Capacity of E10) * (Capacity of E6)/((Capacity of E6) + (Capacity of E7)) E6 = 16 * (8/(8+9)) = 7.53 And similarly: E7 = (Capacity of E10) * (Capacity of E7)/((Capacity of E6) + (Capacity of E7)) E7 = 16 * (9/(8+9)) = 8.47 I can implement this using a Linear Programming solver like glpk by adding explicit constraints that enforce the proportionality between E6 & E7. How should I model this when using a graph model? Thanks in advance for your help and your tolerance of my ignorance :) lbe -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 20.11.2014 19:47, LearnedByError wrote:
I am investigating using maxflow to calculate the max flow from multiple sources based upon network constraints. Is there a way to insure that all nodes upstream of a constraint are reduced proportionately instead of having the constraint being honored by reducing the flow on just the minimum number of nodes needed to meet the constraint value.
Consider the following directed graph: <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/file/n4025881/Network-01.png>
When I calculate the maxflow with the attached program gt-test001.py <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/file/n4025881/gt-test001.py> , I receive the following results (minus the super nodes and reformatted for clarity).
max flow = 39.0 E6 = 8.0 E7 = 8.0 E8 = 11.0 E9 = 12.0 E10 = 16.0 E11 = 21.0 E12 = 39.0
However, the treatment that I am looking for results in: max flow = 39.0 E6 = 7.53 E7 = 8.47 E8 = 11.0 E9 = 12.0 E10 = 16.0 E11 = 21.0 E12 = 39.0
In this case V1 and V2 can deliver 17 but is restricted to 16 by E10 on the outbound side of V3. I want to reduce V1 & V2 proportionately to their capacity such that
E6 = (Capacity of E10) * (Capacity of E6)/((Capacity of E6) + (Capacity of E7)) E6 = 16 * (8/(8+9)) = 7.53
And similarly:
E7 = (Capacity of E10) * (Capacity of E7)/((Capacity of E6) + (Capacity of E7)) E7 = 16 * (9/(8+9)) = 8.47
I can implement this using a Linear Programming solver like glpk by adding explicit constraints that enforce the proportionality between E6 & E7.
How should I model this when using a graph model?
Unfortunately, this is not possible with the current algorithms implemented in the library. Constrained max-flow is a whole different beast, which requires different approaches. The algorithms implemented are guaranteed to compute the correct maximum flow, and provide *one* possible distribution of the residuals. You are on your own to find alternative ones. However in your case it does not seem very difficult to change things a posteriori: You can always redistribute the flows among the sources in any way, as long as the remaining edges are not affected. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (2)
-
LearnedByError -
Tiago de Paula Peixoto