max-flow at max-cost

Question

I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum flow at the maximum cost (or gain).

I'm planning to solve this problem by negating the arc costs and then to compute the maximum flow at the minimum cost.

So, my question concerns to prove or refute if this technique is valid; that is if the negated result of minimum cost after solving the max-flow/min-cost on the transformed network corresponds to the minimum cost. I would use a cancel cycle algorithm.

Thanks in advance for any help

Answer 1

If you are requiring the flow to be a max-flow, this approach is valid; the max-flow at the min-cost of the transformed network must correspond to the max-flow at the max-cost of the original network. So you can just run a min-cost algorithm on the transformed network with the required flow being the max-flow.

The only question is if the min-cost algorithm you want to use can handle negative edge costs. For what it's work, the Wikipedia article on Minimum-Cost Flow states that "most minimum-cost flow algorithms supporting edges with negative costs."

But for this approach to be valid, you must require the max-cost flow to be a max-flow, because it is not true that max-cost flows will always be max-flows. Imagine a network where it is more costly for flow to travel along some cycle, which blocks any flow from getting from the source to the sink. So then calling min-cost max-flow on the transformed network will not give the correct answer.