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.

  • $\begingroup$ You have stocks and you have demands, but what is the question? What output are you looking for the algorithm to produce? Is this a decision question, e.g., whether it is possible to satisfy all demands? Is it an optimization problem, e.g., what's the largest number of demands that can be satisfied, or what fraction of them can be satisfied? Something else? I encourage you to edit the question to state explicitly. $\endgroup$ – D.W. Oct 2 '15 at 17:06
  • $\begingroup$ It is already stated in the topic: "How to check the ability to satisfy demand?" so the primary goal is a boolean answer "able/not able". Fraction is nice to know but not required. In real world it is more complicated, but for this simplified case Tom's suggestion is exactly what I'm looking for. $\endgroup$ – lifecoder Oct 3 '15 at 6:29

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).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.