What is a good local heuristic for dynamic discrete node flow control?

Question

Suppose you have a set of nodes. Some nodes are producers, some are consumers, and some are routers. Each node has a maximum throughput which defines the maximum number of units it can accept per day, and also the maximum number of units it can send per day (in this case accepts and sends do not interfere with each other). Each node also has a storage capacity for units, allowing them to deal with variations in flow. Also, each node may only be out-connected with up to 8 nearby nodes (on a plane), and the same limit applies to in-connections.

I already have a heuristic which, given a graph, enumerates the nodes and does a good-enough job pushing units to following nodes. It enumerates each node, sending max(ceil(remaining-sendable-units/remaining-following-nodes), remaining-receivable-units-at-receiver) to each target node.

Now I need a way to automatically look at a node, and decide what the graph topology should be in order for good-enough flow. My basic idea was to assign a 'responsibility' to each node, initially equivalent to how many units they consumed. Then adding an edge from n1 to n2 would give some of n2's responsibility to n1. But I quickly found that the difference between the amount a node could consume and the amount a node could accept confused the algorithm and led me in circles.

edit The amount consumed by each producer/consumer can vary over time (below some maximum) and nodes can be added or removed.

Any simple ideas?

Answer 1

If you are looking for a "steady-state" solution, i.e. a solution in which the same flow occurs along a given edge each day, then there cannot be any "stockpiling" of resources at nodes (since that would imply that each stockpile continues to grow at a steady rate, eventually becoming infinitely large).

So in that case, we can forget about the storage capacities of each node, and the problem is very similar to the Maximum Flow problem, which can be solved exactly in polynomial time, without too much difficulty. The Wikipedia link suggests a variety of algorithms -- I suggest starting with Ford-Fulkerson, which isn't too hard to implement (the others may be easier but I haven't implemented them myself).

To actually turn your problem into a Max Flow problem, there is one thing you'll need to do: Max Flow deals with constraints on flows across edges, rather than at nodes. To convert your "node throughput" constraints to "edge throughput" constraints, just turn every node into 3 nodes linked in a line (1 -> 2 -> 3), with the edge between nodes 1 and 2 having capacity equal to the "input capacity" of the node, and the edge between nodes 2 and 3 having capacity equal to the "output capacity" of the node. Then make sure that all inputs to the node are connected to node 1, and all outputs are connected to node 3.

As I said, this will give you a "steady-state" solution. It might be possible that, by specifying a number of days up front and utilizing storage capacity, you can devise a strategy that gives you more throughput for that number of days, although I suspect that someone smarter than myself could prove that even this is not possible. In any case, you cannot do better than the Max Flow solution if you want to have the same flow every in each edge every day.