View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# finding minimum flow when edges have lower bounds on flow

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

9 replies to this topic

### #1jwezorek  Members

Posted 07 November 2013 - 12:27 PM

What algorithm should I use to find the minimum flow of a digraph where the flow across each edge has an infinite upper bound but a non-zero lower bound?

Like this for example:

In the literature this is a minimum cost flow problem. In my case however the cost is the same as a nonzero lower bound on the flow required on each edge so I worded the question as above. In the literature the question would be: what is the best algorithm for finding the minimum cost flow of a single-source/single-sink directed acyclic graph in which each edge has infinite capacity, a non-zero lower bound on flow, and a cost equal to the lower bound on flow.

From my research it seems that the main way people deal with any kind of minimum cost of any kind of network is to set the problem up as a LP problem and solve that way. My intuition, however, is that not having upper bounds on flow ,i.e. having edges with infinite capacites, makes the problem easier, so I was wondering if there is an algorithm specifically targeting this case using more "graphy" techniques than the simplex method et. al.

I mean, if all the costs and lower bounds are 1 as in the above... we are then looking for a flow that covers all edges, obeys flow rules, and isn't pushing too much flow through any path from s to t. This just feels like it shouldn't require an LP solver to me and indeed the Wikipedia article on min cost flows states that "if the capacity constraint is removed, the problem is reduced to the shortest path problem" but I think they are talking about the case in which the lower bounds are all zero.

I can envision an algorithm like Edmonds-Karp for solving this problem in which you start by assigning zero flow to all edges and then successively augment the flow on a shortest-path p from s to t by x, where p contains at least one edge for which the lower bound constraint is not already satisfied and x = min{ lowerbound(u,v) - f(u,v) for all (u,v) in p with lowerbound(u,v) > f(u,v)}. When there exists no path p you are done.

However, finding a shortest-path for which there exists at least one edge that does not meet its lower bound is not as simple as running a BFS over a residual network as in Edmonds-Karp.

I think the best way to do this would be to maintain an analog of the residual network that is something like the set of all edges that are not currently satisfied by the flow unioned with satisfied edges that if you removed them at least one unsatisfied edge would become disconnected from the source of the graph or disconnected from the sink of the graph ... this is hard for me to explain because it isn't entirely clear to me yet but when I work out problems on paper I can tell that there is something like a residual network that can be maintained as you go.

Can anyone help?

Edited by jwezorek, 07 November 2013 - 12:32 PM.

### #2Nypyren  Members

Posted 07 November 2013 - 02:49 PM

It seems like the way the minimum flow constraint works, all you really need to do is assign each edge a cost equal to the maximum number of nodes that it can branch to across any path.  It seems like this can be done in a DAG using dynamic programming from the sink backwards to the source using a breadth-first traversal...

(Am I missing some part of the problem?  I haven't used flow networks before and just did some research before responding just now.)

(Edit) Oh, I see - the outbound flow needs to match the incoming flow as well.  Perhaps you could perform the same traversal sink-to-source and then source-to-sink until there are no more flow violations?

Do you need to find the flows for every edge, or only the minimum flow for the entire graph?  (EX: Your example graph has a minimum of 3... if I'm understanding terminology anyway).  There may be some kind of simpler method based on observations about the graph if you don't actually need to find the flow at every edge.

Edited by Nypyren, 07 November 2013 - 02:57 PM.

### #3Álvaro  Members

Posted 07 November 2013 - 03:00 PM

I was thinking something along the lines of Nypyren's proposal, but I don't know what you would do if you reach a node with three incoming edges and two outgoing edges, all initially set to 1. Which of the two outgoing edges do you increase?

### #4jwezorek  Members

Posted 08 November 2013 - 01:27 PM

Do you need to find the flows for every edge, or only the minimum flow for the entire graph?  (EX: Your example graph has a minimum of 3... if I'm understanding terminology anyway).  There may be some kind of simpler method based on observations about the graph if you don't actually need to find the flow at every edge.

You need to find a flow that meets the lower bound for the edge for each edge so if each edge has a lower bound > 0 then each needs to have flow running through it. You also want flow rules to be obeyed and for total flow to be a minimum.

If you start out by setting the flow across each edge to the lower bound then flow rules will not necessarily be obeyed. For each vertex, you can then calculate the difference between the in-flow and the out-flow, call this number D(V). Then you need to deal with the vetices that have non-zero D(V). For a vertex, v that has negative D(v) you need to augment the flow from the source to v. For a vertex with positive v, you would need to augment the flow from v to the sink. You could do this just by finding a shortest path in both cases and augmenting along the shortest path, but I have no idea if doing this would result in the global minimum.

Also seems like it might be inefficient -- not sure. in the toy case above, assigning the lower bounds as the flow is a decent approximation of the minimum flow but that is because this is a toy example -- imagine there are dozens of vertices or hundreds of vertices with arbitrary lower bounds. For my use case, there will probably be at most something like 60 or 70 edges with 30 more likely but this calculation would need to be performed during every iteration of the game loop (this would be for version 2 of my puzzle game Mondrian which I want to develop for the iPad -- but want to change the fundamental algorithm to what it always should have been)

Edited by jwezorek, 13 November 2013 - 03:36 PM.

### #5Álvaro  Members

Posted 08 November 2013 - 02:39 PM

If v is a vertex such that D(v) is positive, you don't always need to augment a path from v to the sink. If there is a vertex w such that D(w) is negative and there is a path from v to w, you just need to augment the path from v to w, and the total flow is unaffected. If a pair (v,w) in those conditions doesn't exist, you can then find paths from the source to negative-D nodes and from positive-D nodes to the sink and augment them. Whether you pick shortest paths or not is irrelevant: The effect on the total flow is the same.

I don't have a formal proof, but I believe that will work. EDIT: No, never mind: There are cases where you have to be clever in what pairs (v,w) you use.

Edited by Álvaro, 08 November 2013 - 02:49 PM.

### #6Nypyren  Members

Posted 08 November 2013 - 03:26 PM

Are your flows always integers, or can they be reals?  I messed around for a while last night with iteratively solving small graphs (15 verts or less, all planar) on paper, using 1 uniformly as the minimum flow for every edge and forcing all edges to use integer flow values.  I'm guessing that with real-valued flows you'd both have a) more flexibility in fixing violations and b) a harder time finding the optimal minimum total flow.

My technique was:

Initialize all edges with their minumums (1 in my case), adding all vertices that violated D(v) == 0 onto a 'fixme' queue.
While the queue contains vertices
{
v = dequeue a vertex
if (D(v) > 0)
increment an arbitrary successor edge by D(v) and queue that vertex if its new D(w) != 0
if (D(v) < 0)
same thing for for an arbitrary predecessor.
}


I never ran into cases where I got stuck in an infinite loop, but I bet it's possible with certain graph layouts.  There are also cases which can occur where the costs can be decreased after fixing initial flow violations.  To do this, I enumerated each path from source to sink and discarded paths that included an edge that was already assigned its minimum cost, then attempted to decrease edges along the remaining overlapping paths (not a very formal description - I was doing it kind of intuitively by hand).

I'm guessing that there is some information you can precompute about the graph that will dramatically improve decisions about which edges to follow (such as topologically sorting vertices to determine which one is closer to the source/sink, or counting the number of paths from each vertex to the source and sinks to attempt to propagate flow updates into more dense regions of the graph which seem to be easier to keep near their minimums than "bottlenecks", and keeping dominator/postdominator information to figure out if you can quickly distribute flow over a smaller portion of a graph rather than propagate all the way to the source/sinks)

Edited by Nypyren, 08 November 2013 - 03:37 PM.

### #7Álvaro  Members

Posted 08 November 2013 - 07:29 PM

I think I have a solution: Find a [non-minimal] valid configuration (something with D(v)=0 for all v), then try to compute how much you can reduce the flow through each pipe. Since you have a lower bound for the flow through each pipe, the numbers you are trying to compute have maximum values. But these numbers also need to satisfy a condition like D(v)=0, so we have reduced the problem to a maximum-flow problem and we can use the Ford-Fulkerson algorithm.

I don't think you can do better than that.

### #8jwezorek  Members

Posted 09 November 2013 - 02:01 PM

I think I have a solution: Find a [non-minimal] valid configuration (something with D(v)=0 for all v), then try to compute how much you can reduce the flow through each pipe. Since you have a lower bound for the flow through each pipe, the numbers you are trying to compute have maximum values. But these numbers also need to satisfy a condition like D(v)=0, so we have reduced the problem to a maximum-flow problem and we can use the Ford-Fulkerson algorithm.

I don't think you can do better than that.

Yes, this is good ... now I just need a way of finding a feasible flow in a single traversal.

EDIT: Yeah, so I think it can be solved as two max flow problems. The in-flow(v) - out-flow(v) function that I was calling D(v) above can be viewed as node supplies and demands which you can figure out how to satisfy via a max flow problem. you can construct a graph from the original graph as explained here: (where x(v) is what we were calling D(v))

we modify G to obtain a new graph G0 by adding a new source s0, a new target t0, an
infinite-capacity edge t-s from the old target to the old source, and several edges from s0 and to t0.
Specifically, for each vertex v, if x(v) > 0, we add a new edge s0->v with capacity x(v), and if x(v) < 0,
we add an edge v->t0 with capacity -x(v).

such that if you find max flow of the new graph, the flow on the edges in this max flow plus the lowerbounds on the original graph will be an admissible flow on the original graph which you can then minimize with another max flow problem as alvaro explained above.

Edited by jwezorek, 09 November 2013 - 04:30 PM.

### #9Álvaro  Members

Posted 09 November 2013 - 09:58 PM

Computing a feasible flow doesn't seem terribly complicated. For each edge on the graph you can find a path that contains it. Then start with 0 flow for every edge, loop over the edges and add the minimum flow for the each edge to the path that includes this edge. I am not sure if this can be done in "single traversal", because it's late and because it depends on exactly you mean by that. But I think it will be faster than solving another max-flow problem (although I didn't fully follow what you posted).

### #10jwezorek  Members

Posted 10 November 2013 - 11:42 AM

Computing a feasible flow doesn't seem terribly complicated. For each edge on the graph you can find a path that contains it. Then start with 0 flow for every edge, loop over the edges and add the minimum flow for the each edge to the path that includes this edge. I am not sure if this can be done in "single traversal", because it's late and because it depends on exactly you mean by that. But I think it will be faster than solving another max-flow problem (although I didn't fully follow what you posted).

See, I was thinking that finding a feasible flow like this has really bad running time but I think it doesn't at least not relative to max flow. You could just do a complete depth-first traversal and then when you either reach t or reach an already-discovered vertex augment the current path you are on with the max lowerbound of the set of edges that were newly discovered on the current path, going all the way to t each time you do this. This would have running time of something like O(E * Avg. length of paths from s to t).

The algorithm involving two max flows is what you need to do when edges have both lower bounds and upper bounds, as someone is discussing in this power point file

There also turns out to be a small amount of literature on this problem itself -- that is, minimum flow -- not just as a use of max flow or as formulated as minimum cost: see here and here, for example, but all of this material deals with the case in which there are lower and upper bounds. It actually surprises me that there is nothing in the literature about the no upper bound case; it seems like a very practical problem.

Edited by jwezorek, 13 November 2013 - 11:59 AM.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.