SliferSkyd's blog

Min Cost Max Flow with demands
By SliferSkyd, history, 4 weeks ago, In English

Hi all,

I am currently stuck on a problem that can be solved by finding the minimum cost of the maximum flow in a graph with lower and upper bounds on edge capacities.

My problem combines aspects of minimum-cost flow and maximum flow with node demands. I have also come across the "Minimum Cost b-Flow" problem, which is similar, but it does not maximize the total flow.

Does anyone have any ideas for solving this problem? Thanks in advance.

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://cp-algorithms.com/graph/min_cost_flow.html

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Perhaps you can transform an instance of your problem into vanilla min-cost-flow. For an edge with feasible range of capacities $$$[a, b]$$$, imagine that you allocate $$$a$$$ flow on this edge automatically. Do this for all edges. This determines some "upfront cost", which you can set aside for now, and leaves you with a almost a min-cost-flow instance with new edge capacity $$$b - a$$$ for this edge. There are only 2 issues:

  1. Pre-allocating these flows means some nodes have non-zero net flow to begin with. This is fine, as some min-cost-flow algorithms already account for so-called "supply" and "demand" nodes (https://developers.google.com/optimization/flow/mincostflow).
  2. It remains to be shown that a max-flow on the transformed graph translates into a max-flow on the original graph, and also that, among all maximum flows on one graph, ordering these flows by cost yields the same ordering as you would get with the transformed flows on the other graph.

I didn't prove 2, but it feels plausible.

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh wait, I left off two things.

    1. The above transformation may yield demand at your Source and/or supply at your Sink. Set both of those quantities to 0. Now, if $$$E$$$ is the net excess supply of the graph, it might be that $$$E \neq 0$$$. If $$$E > 0$$$, create a new Source, with supply $$$E$$$ and a single edge of cost $$$0$$$ and "infinite" capacity to the original Source. Likewise, if $$$D < 0$$$, create a new Sink in the same fashion.

    2. The resulting problem is actually just a min-cost-flow, whereas you require a min-cost-max-flow. We can do one more polytime reduction to fix this. Say we add a supply $$$\sigma$$$ to the Source and a demand $$$\sigma$$$ to the Sink. Min-cost flows on this graph, translate to the min-cost-$$$\sigma$$$-flows on your original graph. Also, the cost of these flows only differ by the "fixed cost" we set aside earlier. So, just binary search over $$$\sigma$$$.

    → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It's similar with "no cost max flow with demands", but every extra edges you add for demands (i.e. not in the original graph) should have a cost of 0.

→ Reply