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

what algorithm should use find minimum flow on digraph there lower bounds, not upper bounds on flow? such simple example:

in literature minimum cost flow problem. in case cost same nonzero lower bound on flow required on each edge worded question above. in literature question be: best algorithm finding minimum cost flow of single-source/single-sink directed acyclic graph in each edge has infinite capacity, non-zero lower bound on flow, , cost equal lower bound on flow.

from research seems main way people deal kind of minimum cost of kind of network set problem lp-type problem , solve way. intuition, however, not having upper bounds on flow ,i.e. having edges infinite capacites, makes problem easier, wondering if there algorithm targeting case using more "graphy" techniques simplex method et. al.

i mean, if costs , lower bounds 1 in above... looking flow covers edges, obeys flow rules, , isn't pushing flow through path s t. feels shouldn't require lp solver me , indeed wikipedia article on min cost flows states "if capacity constraint removed, problem reduced shortest path problem" think talking case in lower bounds zero.

also there open source c/c++ code minimum cost flow anywhere? googling available find can either set problem lp problem myself , solve open source lp solver, or use lemon provides several algorithms min-cost flow. boost graph library not include implementation far can tell.

is there else?

in absence of upper-bounds, easiest way -- easiest implement, understand, , reasonably efficient -- find minimum flow of graph following:

1. find feasible flow, i.e. flow satisfies flow rules , lower-bounds on flow isn't minimum flow. can accomplished doing depth-first traversal of graph, keeping track of current path traverse, , upon visiting discovered node or t, target node, augmenting flow on current path maximum lower-bound of unsatisfied edges on current path way t.

2. turn feasible flow minimum flow solving max flow problem. need find maximum flow on graph has capacities equal flow(e) - lower-bound(e), flow(e) means flow feasible flow. maximum flow subtracted feasible flow minimum flow.

a version of above can performed in case in graph has upper-bounds on flow. in case step 1. more complicated can solved performing initial max flow computation on specially constructed graph.