algorithmoptimizationnetwork-flow

Optimal Flow Distribution


I've searched stackoverflow and google but I haven't found someone with quite the same type of problem.

Optimal distribution of power plants on a city seemed like the closest solution to this problem but I believe my problem is simplier than the question there and therefore would have a better solution than bruteforce.

The problem is this: I have 9 cities, each producing power and using power. Each city is connected to the other 8 cities. How can I determine the best way to send excess power to the cities that need it with the minimum amount of energy transfered?

I've tried to do this problem with network flow, utilizing multiple sources and sinks but it does work correctly.

Thanks!


Solution

  • Look at this article. That is how you can reduce your problem to min-cost max-flow.

    For every city, calculate demand d as usage - production. Group cities by d=0, d<0 and d>0. Let all connections have infinite capacity. Then add two new nodes, sink and source. Add edges between source and d<0 nodes, with capacity |d|. Add edges between d>0 and sink nodes, with capacity d. Now you have single-source single-sink network, and you can apply any min-cost max-flow algorithm to find the solution.