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?

Unrelenting

nice star on the title, lol – Norikonorina

I don't actually know where that star came from... – Unrelenting

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.

Unrelenting

This approach seem to work. Can someone explain why it holds that minimum_flow = feasible_flow - max_flow, as stated in the above answer? I'm not sure why this is true – Wildfowl

if you are taking away as much flow as you can from a feasible flow what you are left with has to be a minimal flow by definition of minimal flow. If you could take away more flow it wouldn't be minimal but you can't because you took the maximum amount possible away. – Unrelenting

This doesn't work for all digraphs. The actual solution using a max flow algorithm can be found, for example, here: cs.rhul.ac.uk/books/dbook/mainNP.pdf – Upholstery

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.

Therontheropod

Setting up a library like LEMON is much more complicated than a solver, it's just dijkstra's / SPFA, F times. If anyone else is looking for a soln, github.com/ruippeixotog/algo-lib/blob/master/… , would be easier. (Lemon's NetworkSimplex method is heuristically up to 10x faster on sparse / random graphs, but this is unnecessary for most purposes, and it has weaker Big-O bounds in worst cases) – Epidaurus

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.

Sackett

So f is the flow assignment in which the flow across each edge is just equal to the lower bound? – Unrelenting

f will not be a legal flow meaning for a given node the incoming flow will not equal the outgoing flow. Therefore merely augmenting f along the shortest path from s to t is not going to necessarily result in a legal flow. What about nodes of f where conservation of flow is not satisfied that are not on the shortest path, for example. – Unrelenting

Yes you are right. I try to adapt the solution right now, I will edit the answer if it works. – Sackett

I'm not following, sorry ... for the example problem I posted a diagram of, what would the minimal assignment look like and what multiflow problem would it yield? Can you post a diagram of the step of the algorithm you propose -- I could figure it out from that. – Unrelenting

I added the example of your problem (I assume there is no required flow at the sink in the initial problem). – Sackett

There is no required flow on any of the nodes in the problem only edges. You are reducing the problem to a multi-sink minimization problem with no capacities or lower bounds so it turns it into shortest path? Is this correct? – Unrelenting