patternMinor
Algorithm for arranging elements into different sized buckets
Viewed 0 times
bucketselementsintoarrangingsizedalgorithmdifferentfor
Problem
I have a set of items. For each item, there is a list of buyers I can sell it to and a corresponding price they will pay me. For example:
I need to assign each item to one buyer so as to maximise the amount of money I make. If it were as simple as this, the assignments would go
However, I also need to try to meet quotas of items for the buyers.
So these quotas might be:
i.e. I need to sell a total of 99 items to Bob, 30 to Sue etc.
The quotas will not cover all items, so it could be that of a total of 1000 items, only 800 are forced to follow the quotas and the remainder can go to whichever buyer pays the highest amount.
The problem then, is to assign the items in such a way as to maximise revenue while still filling the quotas.
In some cases it will not be possible to meet the quotas because not every item can be assigned to every buyer - for example, if there were only the 3 items above and Joe had a quota of 2, I wouldn't be able to meet it as only item3 can be sold to him. It seems to me two types of solution are available in this case, either of which I'm open to.
I've thought of a few strategies, but none that has the mathematical rigour I'd like.
Also, I'm not really sure what flavour of problem this is, so if anyone can suggest a better title for this que
item1: item2: item3: item4:
john: 17 john: 19 bob: 42 ...
bob: 23 mick: 22 mick: 44
sue: 19 liz: 24 sue: 38
liz: 20 joe: 45I need to assign each item to one buyer so as to maximise the amount of money I make. If it were as simple as this, the assignments would go
item1: bob
item2: liz
item3: joe
...However, I also need to try to meet quotas of items for the buyers.
So these quotas might be:
bob: 99
sue: 30
john: 45
...i.e. I need to sell a total of 99 items to Bob, 30 to Sue etc.
The quotas will not cover all items, so it could be that of a total of 1000 items, only 800 are forced to follow the quotas and the remainder can go to whichever buyer pays the highest amount.
The problem then, is to assign the items in such a way as to maximise revenue while still filling the quotas.
In some cases it will not be possible to meet the quotas because not every item can be assigned to every buyer - for example, if there were only the 3 items above and Joe had a quota of 2, I wouldn't be able to meet it as only item3 can be sold to him. It seems to me two types of solution are available in this case, either of which I'm open to.
- Find a solution that minimises the number of unfilled quota positions and maximises revenue.
- Run a preliminary algorithm that checks if the quotas are fillable. If they aren't, simply fail at that point (under the assumption that some user will then manually tweak the quotas and run the process again). If they are, then find a solution that fills them and maximises revenue.
I've thought of a few strategies, but none that has the mathematical rigour I'd like.
Also, I'm not really sure what flavour of problem this is, so if anyone can suggest a better title for this que
Solution
Your problem can be solved in polynomial time.
You mention two possible goals and say you'd be happy with a solution to either. The first goal isn't well-defined, so I'll describe a solution to the second goal. I can see two possible approaches: (a) use integer linear programming (ILP), (b) use network flow. The former will be simple to implement, and is flexible (if you later have new constraints it'll be easy to add them), but if you're unlucky, the running time could be exponential. The second has the advantage of running in polynomial time, but it might be more work to implement. fade2black described the ILP approach well, so I'll describe the network flow approach.
To solve the problem with network flow, formulate this as a minimum-cost network circulation problem. In network flow, each edge has a capacity: an upper bound on the amount of flow through that edge. Minimum-cost circulation also allows you to specify a lower bound on the amount of flow through that edge, and the per-unit cost of sending flow through that edge.
We'll construct a directed graph with a source node $s$, a node $u_i$ for each item, a node $v_j$ for each buyer, and a sink node $t$. Add edges $s \to u_i$ with cost 0, lower bound $1$, and upper bound (capacity) $1$. Add edges $u_i \to v_j$ with cost equal to the negative of the amount buyer $j$ will pay for item $i$, lower bound $0$, and upper bound (capacity) $1$. Add edges $v_j \to t$ with cost 0, lower bound equal to the quota for buyer $j$, and upper bound $\infty$. Finally, add an edge $t \to s$ with cost 0, lower bound 0, and upper bound $\infty$. Now look for the minimum-cost circulation in this graph. That will correspond to a solution that maximizes the revenue, subject to the requirement that all quotas must be filled.
You mention two possible goals and say you'd be happy with a solution to either. The first goal isn't well-defined, so I'll describe a solution to the second goal. I can see two possible approaches: (a) use integer linear programming (ILP), (b) use network flow. The former will be simple to implement, and is flexible (if you later have new constraints it'll be easy to add them), but if you're unlucky, the running time could be exponential. The second has the advantage of running in polynomial time, but it might be more work to implement. fade2black described the ILP approach well, so I'll describe the network flow approach.
To solve the problem with network flow, formulate this as a minimum-cost network circulation problem. In network flow, each edge has a capacity: an upper bound on the amount of flow through that edge. Minimum-cost circulation also allows you to specify a lower bound on the amount of flow through that edge, and the per-unit cost of sending flow through that edge.
We'll construct a directed graph with a source node $s$, a node $u_i$ for each item, a node $v_j$ for each buyer, and a sink node $t$. Add edges $s \to u_i$ with cost 0, lower bound $1$, and upper bound (capacity) $1$. Add edges $u_i \to v_j$ with cost equal to the negative of the amount buyer $j$ will pay for item $i$, lower bound $0$, and upper bound (capacity) $1$. Add edges $v_j \to t$ with cost 0, lower bound equal to the quota for buyer $j$, and upper bound $\infty$. Finally, add an edge $t \to s$ with cost 0, lower bound 0, and upper bound $\infty$. Now look for the minimum-cost circulation in this graph. That will correspond to a solution that maximizes the revenue, subject to the requirement that all quotas must be filled.
Context
StackExchange Computer Science Q#80160, answer score: 3
Revisions (0)
No revisions yet.