I am recently preparing for the acm-icpc contest. Here I want to know how to find the minimum flow with the least cost given the condition that each edge in the graph has a capacity C, a cost V, and a lowerbound flow L (L ≤ C).
A:
First, I'm not sure what "minimum flow with the least cost" means, but I suspect you just mean "flow with the least cost".
Second, the lower bound flows means it is non-trivial to find an "legal flow", which is a flow where conservation of mass is respected, i.e. the sum of the inbound flows is equal to the sum of the outbound flows for all nodes except the source and the sink. (Usually flow problems have L=0 which means that the zero flow is legal.) In fact, there are choices of L and C for which no legal flow exists.
I think you could find a legal flow by starting with a flow which is equal to L on each edge. Some nodes in the graph will then have a surplus flow, and some will have a deficit flow. You can augment the flow by finding a (below capacity) path from a surplus node to a deficit node and pushing more flow along that path. Repeat until all surpluses are zero, or you can't find such a path (in which case no legal flow exists).
Once you find an admissible flow, then Ford-Fulkerson or preflow-push algorithms can then optimize your flow (modify it to lower total cost).
Keith Randall
2010-09-16 16:33:01
A:
Hi, and good luck on your competition!
I'm a little concerned that the first solution proposed can, at best, help you find minimum max flow, which is on track to what you're looking for, but not quite the same.
I took a class taught by Robert Tarjan. He happens to have helped develop a method of deriving minimum flows called: "cycle canceling". Here is a great lecture posted by Kevin Wayne, a senior lecturer at Princeton (with Tarjan): http://www.cs.princeton.edu/~wayne/papers/ratio_talk.pdf
Min-mean circuit canceling in particular will help you to find min flows.
If you look over those two papers and still would like to discuss, please let me know.
A:
I think your question is not well specified.
Are C, L and V single constant that apply to all edges or are they vector? Since you are providing a minimum flow for edges, I am assuming your graph has directed edges such that flow is possible only in one direction. The other point that needs clarification is that the cost V, is it per unit of flow? I am assuming yes, since otherwise the cost of any flow would be E.V for L > 0.
So with those assumptions, you want min cost circulation problem.