World's most popular travel blog for travel bloggers.

# How to check the ability to satisfy demand?

, ,
Problem Detail:

We have Stocks in several discrete positions, let say:

``A    B   C 40   20  80 ``

And Demand, which may be satisfied by one or more Stock positions (if no specified then it would accept any Stock).

Demand for A=20 may be satisfied from A Stock only, and depletes 20 units from it. Demand for AB=20 may be satisfied from any of the A abd B Stocks, and may take partially from both, without any proportion limitations.

So for the Stocks example above:

This Demand may be satisfied (10 strict from A, 20 strict from B, and 30 AB would take from both)

``AB  B   A 30  10  20 ``

And this may not (insufficient B Stocks)

``AB  B   B 30  10  20 ``

This sounds like a more or less common problem which should have a known solution. I would be happy with any reference or idea. Also if the solution is resource heavy a cheaper approximation would be great.

###### Answered By : Tom van der Zanden

You can formulate this as a maximum flow problem, which you can solve using standard techniques.

Turn every stock in to a source node with capacity equal to the amount of stock. Any demand gets turned in to a sink with demand equal to its demand. Add edges between stocks and demands if the stock can fulfill the demand.

If you don't want to have more than one sink or source that is possible too: you create the stock and demand nodes as before, and create an edge between the sink and all stock nodes (with capacity equal to the amount of stock available), similarly create an edge between all demand nodes and the sink (with capacity equal to the demand).