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.
Edited by jwezorek, 07 November 2013 - 12:32 PM.