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.