I'm looking for some hints how to solve the following problem:

Basically, it's a minimum cost flow problem in a digraph with nonnegative arc costs.
All arcs have an upper capacity bound that is positive.
Most arcs have a lower bound equal to zero.
But on SOME arcs the lower bound equals minus infinity, they can carry an arbitrary negative amount of flow.

I looked up in several textbooks which deal with network flow problems. But every author assumed that the lower bound is finite, therefore they did the standard reduction to represent it as an equivalent problem with nonnegative flow on each arc. But I do not see how I can apply this to my problem.

I dont want to use a linear programming solver, I'm looking for a combinatorial algorithm. Maybe some of you have some links or ideas how to solve that problem...