What algorithm should be used to find the minimum flow on a digraph, where there are lower bounds, but not upper bounds of the flow?

Question

What algorithm should I use to find the minimum flow on a digraph, where there are lower bounds but not upper bounds of the flow? For example, this simple example:

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

From my research, it seems that the main way that people cope with any minimum cost of any network is to set the problem as an LP-type of problem and solve this way. My intuition, however, is that it does not have upper bounds in the flow, i.e. with ribs with infinite capacities makes the task easier, so I was wondering if there is an algorithm specifically designed for this case, using more “graphical” methods than the et simplex method. and etc.

I mean, if all costs and lower bounds are 1, as in the above ..., we then look for a thread that covers all edges, obeys the flow rules and does not push too many threads along any path from s to t. It just seems like I should not need an LP solver, and indeed the Wikipedia article on minimum cost flows states that “if the capacity limit is eliminated, the problem boils down to the shortest path problem”, but I think they are talking about a case when the lower bounds are zero.

Also, is there open source C / C ++ code for minimal flow anywhere? From googling, which is available, I find that I can either solve the problem as an LP problem myself, or solve it using an open source LP solution, or I could use LEMON, which provides several algorithms for the stream at a low cost. As far as I can tell, the acceleration graph library does not include an implementation.

Is there anything else?

Answer 1

In the absence of upper bounds, the easiest way — the easiest way to implement it, to understand and reasonably efficiently — is to find the minimum chart flow as follows:

• Find a valid stream, i.e. A stream that satisfies the stream rules and the lower bounds of the stream, but is not necessarily the minimum flow. This can be done by completing the first step to cross the graph, tracking the current path while passing, and visiting the previously discovered node or t, the target node, increasing the flow along the current path with the maximum lower boundary of unsatisfied edges on the current path up to t.

• Turn the allowable stream to minimum stream, solving the problem of maximum stream. You need to find the maximum flow on the graph, which has powers equal to the flow (e) - the lower boundary (e), where the flow (e) means the flow from the allowable flow. This maximum flow, subtracted from the allowable flow, will be the minimum flow.

The version above can also be performed in the case where the graph also has upper bounds on the flow. In this case, step 1. is more complicated, but it can be solved by performing the initial calculation of the maximum flow on a specially constructed graph.

Answer 2

Writing a solver is nontrivial.

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

For information on LEMON, see http://lemon.cs.elte.hu/trac/lemon .

For more information on network flow at minimal cost, see http://lemon.cs.elte.hu/pub/doc/1.3/a00607.html .

Answer 3

Add all the "lower bounds" of the flows on each edge: in any case, any valid solution is required.

For each node n in the topological order (i.e., along the edges) from the shell t , if the sum S- of what goes on the edge is greater than the sum S+ of what then adds the stream S+ - S- along all the edges of the shortest path between s and t (create a shortest path list, doing this for efficiency).

Then you have a “minimal” set (in the sense that it is necessary in every possible solution), for example, S+ - S- non-negative in each node, and the minimum capacity is performed on each edge.

Then the problem is reduced to a multipoint problem in the same chart structure:

• same source
• no capacity limit;
• each node, where S+ - S- strictly positive, becomes a receiver with the required stream S+ - S- .
• the initial receiver (having the required stream F ) becomes the receiver with the stream F - S- if FS- non-negative (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 a minimum capacity of 1 for each edge, and I believe that a minimum flow is not required in stream t .

First assign 1 to each edge.

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

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

only negative for x4 ; we add 1 to each edge on the shortest path from x4 to t , in this case to the edge (x4, t) .

Now S+ - S- non-negative for each node and positive only for x1 ; the problem boils down to a multipoint problem (in this case it is a simple stream problem), where the requested stream is 1 at x1 and the source is still s .