Complexity,algorithms and applications of the integer network flow with fractional supplies problem

We consider here the integer minimum cost network flow when some of the supplies are fractional. In the presence of fractional supplies it is impossible to satisfy the flow balance constraints, creating an imbalance. We present here a polynomial time algorithm for minimizing the total cost of flow and imbalance penalty. We also show that in the presence of a constraint that bounds the imbalance the problem is NP-hard, but efficiently solvable for a fixed number of fractional supplies.