title: What algorithm should I use to find the minimum flow on a digraph where there are lower bounds but not upper bounds on flow?
body: <p>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:</p>
  
  <p><img src="https://i.stack.imgur.com/XVqf6.png" alt="Diagram of simple example. Source: &lt;jwezorek.com/wp-content/uploads/2013/09/min_flow.png&gt;"></p>
  
  <p>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.</p>
  
  <p>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 <a href="https://en.wikipedia.org/wiki/LP-type_problem" rel="noreferrer">LP-type problem</a> 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. </p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>Is there anything else?</p>