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

  • $\begingroup$ The mathematics doesn't care whether you call it a cost, a gain or an elephant. I don't know what you mean by "negating the arc costs" (literally replacing $x$ with $-x$?) but it seems very unlikely that what you're describing would work. $\endgroup$ – David Richerby Jun 14 '16 at 12:33
  • $\begingroup$ There is a well-known network flow algorithm for computing a max flow at the min cost. I have a situation where I have a finite gas flow to be distributed through several oil wells. Say us that the more gas passes through a well the more oil production you have. So I interpret this situation as to distribute the gas flow in a way that maximises the sum of oil production. My approach is to negate the production and then to compute the max flow at the minimum cost. The negated of the total cost would be the maximum production. All that I wish is validate this approach. Thanks for the interest $\endgroup$ – lrleon Jun 14 '16 at 12:45
  • $\begingroup$ And of course, if that approach wouldn't work, why? $\endgroup$ – lrleon Jun 14 '16 at 12:47
  • 1
    $\begingroup$ If all capacities are equal to one, and your source and destination have a single outgoing/ingoing edge, min-cost-max-flow is equivalent to shortest path. Max-cost-max-flow would be equivalent to longest path. This should concern you. $\endgroup$ – Mihai Calancea Jun 14 '16 at 15:07
  • $\begingroup$ That is more or less the intuition under my reasoning. I know the original network es acyclic and that finding a shortest path on -G (G with its weights negated) is equivalent to finding a longest one on G. But before starting to code, I would like to be sure that my reasoning is correct. Of course, on the residual network will appear lots and lots of negative cycles, but I think successive canceling would eventually leave the net without negative cycles and at this moment the flow assignations would produce the maximum $\endgroup$ – lrleon Jun 14 '16 at 15:26

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.