Is there any algorithm for this kind of a problem?

[legend986]

I have a dataset from which I want to distribute some resources amongst some participants. I have the following say:

Seller:
Group ID | Serial Number | Stock

Buyer:
Group ID | Serial Number | Demand

There are a number of buyers and seller and I have to allot proper sellers to buyers in the most optimal way based on the following constraints:

1. For a buyer and a seller, the group ID should match. I mean, a seller can sell to a buyer only if they are in the same group.

2. The buyer's demand could be greater than or less than or equal to the stock available.

So for a situation like this:

Sellers:
Group ID | Serial Number | Stock
1 | 1 | 10
1,2 | 2 | 10
2 | 3 | 3

Buyers:
Group ID | Serial Number | Demand
1 | 4 | 10
2 | 5 | 5

If Buyer 4 buys from seller 2, then Buyer 5 is left with no stock at all because Seller 3 has only 3 left. But the desired output is that Buyer 4 should've bought stock from Seller 1.

I'm currently trying out a brute force method and am really not sure if I can address so many complexities. Does this problem fit a known model or something?

[Kheun]

Seller 1 and 2 have the same number of stock. Why can't buyer 5 buys from seller 1?

[legend986]

I'm sorry... Updated the problem... Hope I did it right this time...

[msg555]

What exactly is it that you are trying to optimize. If you are trying to maximize the number of things traded then this is a max flow problem.

http://en.wikipedia.org/wiki/Maximum_flow_problem

In your instance of the problem, you have a bipartite graph where one set of people are the sellers and the others are the buyers.

The buyers will be connected to the super-source with capacity equal to their demand. The sellers will be connected to the super-sink with capacity equal to the amount they can sell. An edge with infinite capacity will connect buyer x with seller y if buyer x is allowed to buy from seller y.

[legend986]

Oh Thank You... So its called max flow problem? I'm trying to optimize the resource distribution. For example, take the above scenario:

If Buyer 4 buys from seller 2, then Buyer 5 is left with no stock at all because Seller 3 has only 3 left. But the desired output is that Buyer 4 should've bought stock from Seller 1 so that Buyer 5 could've bought the stock from Seller 2.

I'm trying to get the optimal resource distribution i.e. something like "Buyer X1 should buy some x stock from Seller Y1, Buyer X2 should buy so and so stock from Seller Y2 and so on" in an optimized way so as to have maximum satisfied buyers in the list.

[msg555]

hmm, are you trying to maximize the number of things sold, or the number of buyers whose demand was completely satisfied?

The latter isn't solvable with maxflow (as far as I can tell)

btw, this article explains a bit of the theory and implementation of maximum flow http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow

[legend986]

Thank you so much for the article. I started reading that but just incase, I'm not sure if this fact was made clear but I would like the buyer to have their entire stock. In other words, no partial stock is acceptable for a buyer but a seller can sell as much as he wants and a buyer can buy only from one seller.

[msg555]

well, if buyers could buy from multiple sellers and only partially buy their demand this would be a max flow problem. The additional constraints make this appear quite a bit harder. How many buyers and sellers do you need this algorithm to work quickly for?

[legend986]

Well, I have approximately 85 buyers and 68 sellers... Do you think that is a small set to work for?

[msg555]

I'm sorry, I can't think of any polynomial solution to your problem. My best suggestion now is just to implement a Branch and Bound solution and hope that it can run fast enough for most inputs.

http://en.wikipedia.org/wiki/Branch_and_bound

[legend986]

Thank you. I've been reading the algorithms but I am unable to incorporate this into those algorithms. Just in case I have made a more precise definition of the problem:

There are some buyers and some sellers. The business has to go in the following way:

1. Each buyer can buy only from a set of sellers
2. Each seller can sell only to a set of buyers
3. The buyer has a particular demand
4. The seller has some stock left
5. The mapping is n to n. That is, a buyer can buy resources from a set of sellers

The goal is to maximize the sales in a way that maximum buyers can be satisfied.

[msg555]

I'm not really sure what you mean by 5. Anyway, a good start to a solution would be to write a recursive brute force method. Write a recursive procedure that tries to match buyers to a given seller in every way possible. The procedure should take the current buyer you are working with and the subset of sellers that have been used so far.

[Lindley]

If each buyer needs to buy from only one seller (which I *don't* see in those five points), then you'd have a bipartite matching problem, essentially.

But as it is, I think max-flow is the way to go. Unless there's a subtlety that isn't getting across.

[msg555]

I don't see how you could set up the graph to get this into a max-flow problem. I also don't see how you could set this up as a bipartite matching because each buyer has a different buying power.

[Lindley]

Upon further reflection, (5) means that a single buyer can buy from multiple sellers, and a single seller can sell to multiple buyers.

How you'd flip things around to maximize satisfied buyers rather than amount sold is a bit unclear, though. Max flow doesn't include much of a provision for "fill this route first".

[legend986]

I'm sorry for the delay in replying. Instead of using a max flow or some other algorithm, I'm thinking of using something like this (heuristic):

Buyers = {b1,b2,...,bn}
Sellers = {s1,s2,...,sm}

Each buyer bk has access to a subset of sellers Sk

foreach buyer in Buyers
---- select a random seller in the group of sellers, this buyer has access to
---- if the seller was already selected, then select another random seller until one seller is fixed to this buyer
---- As a seller is selected, mark this seller so that no other buyer can select this seller
---- If all the sellers are exhausted, mark the buyer as unsatisfied
---- goto next buyer
end for

I'm not sure if I am able to convey what I'm thinking of but now, I don't want an optimum solution, but just a possible solution. Do you think this would work well?

[msg555]

I think that would work alright if you don't need an exact answer. In addition, you could run that algorithm multiple times and randomly shuffle the buyer and seller arrays each time.