What algorithm should I use to find the minimum flow on a digraph where there are lower bounds but not upper bounds on flow?

Question

What algorithm should I use to find the minimum flow on a digraph where there are lower bounds, but not upper bounds on flow? Such as this simple 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-type 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.

Also is there open source C/C++ code for minimum cost flow anywhere? From googling what is available I find that I can either set the problem up as an LP problem myself and solve with an open source LP solver, or I could use LEMON which provides several algorithms for min-cost flow. The boost graph library does not include an implementation as far as I can tell.

Is there anything else?

Answer 1

In the absence of upper-bounds, the easiest way -- easiest to implement, understand, and that is reasonably efficient -- to find the minimum flow of a graph is the following:

1. Find a feasible flow, i.e. a flow that satisfies flow rules and lower-bounds on flow but isn't necessarily a minimum flow. This can be accomplished by doing a depth-first traversal of the graph, keeping track of the current path as we traverse, and upon visiting a previously discovered node or t, the target node, augmenting the flow on the current path with the maximum lower-bound of the unsatisfied edges on the current path all the way to t.

2. Turn the feasible flow into a minimum flow by solving a max flow problem. You need to find the maximum flow on the graph that has capacities equal to flow(e) - lower-bound(e), where flow(e) means flow from the feasible flow. This maximum flow subtracted from the feasible flow will be a minimum flow.

A version of the above can also be performed in the case in which the graph also has upper-bounds on flow. In that case step 1. is more complicated but can be solved by performing an initial max flow computation on a specially constructed graph.

Answer 2

Writing a solver is non-trivial.

See the LEMON library (part of COIN-OR). It has a number of highly optimized algorithms for the min cost flow problem. You can choose which algorithm works best on your data.

See http://lemon.cs.elte.hu/trac/lemon for information about LEMON.

See http://lemon.cs.elte.hu/pub/doc/1.3/a00607.html for details about min cost network flow.

Answer 3

Add all the "lower bounds" of the flows on each edge: any feasible solution will need that anyway.

For each node n in the topological order (i.e. following the edges) from the sink t, if the sum S- of what goes in the edge is greater that the sum S+ of what goes out, then add the flow S+ - S- on all edges of the shortest path between s and t (construct the list of shortest path while doing this for efficiency).

Then, you have a 'minimal' assigment (in the sense that it is needed in every feasible solution) such as S+ - S- is nonnegative at each node and the minimal capacity is satisfied on each edge.

The problem then reduce to a multiflow problem on the same graph structure:

• the source is the same;
• there are no capacity limit;
• every node where S+ - S- is strictly positive becomes a sink with required flow S+ - S-.
• the initial sink (which had a required flow F) becomes a sink with flow F - S- if F-S- is nonnegative (otherwise the initial constraint will be satisfied by any solution).

Edit: for your problem, the graph looks like this

     x1 -- x2
   /   \     \
 s      \     t
   \     \   /
     x3 -- x4

with minimal capacities 1 for each edge, and I suppose there is no minimal flow required at the sink t.

First assign 1 to each edge.

The difference S+ - S- for each node (except, of course, s and t) is:

x1: 1
x2: 0
x3: 0
x4: -1

the only negative one is for x4; we add 1 to every edge on the shortest path from x4 to t, in that case to the edge (x4, t).

Now S+ - S- is non-negative for every node, and positive only for x1; the problem reduce to a multiflow problem (in that case it is a simple flow problem) where the requested flow is 1 at x1, and the source is still s.