Algorithm for arranging elements into different sized buckets

Question

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:

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:  45  

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

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.

1. Find a solution that minimises the number of unfilled quota positions and maximises revenue.
2. 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 question, feel free to edit :)

For context, this is a work-related requirement for an energy broker that wants to assign customers (the 'items' in my example) across its pool of energy suppliers.

Edit: If this can be thought of as a form of the Generalized Assignment Problem (as per @fade2black's) answer, it may be helpful to tweak things in this way: items that can't be sold to a particular buyer are assigned a revenue of 0 with respect to that buyer.

So in other words, every item can be sold to every buyer, but some have a revenue of 0. Presumably any optimisation algorithm will then tend to filter these 0-revenue combinations out.

Answer 1

Your problem is very similar to the Generalized Assignment Problem which is $NP$-complete.

The Generalized Assignment Problem states, using the terminology of the Knapsack Problem: given $n$ items and $m$ knapsacks with profit $p_{ij}$ and weight $w_{ij}$ if the item $i$ is assigned to the knapsack $j$. Also, each knapsack $j$ has capacity $c_j$. The goal is to put each item into a knapsack so that the total profit would be maximum and the total items capacity in each knapsack $j$ would not exceed $c_j$. Mathematically $$\text{Maximize } \sum_{j=1}^{m}\sum_{i=1}^{n}{p_{ij}}x_{ij}$$ $$\text{Subject to } \sum_{i=1}^{n}{w_{ij}}x_{ij} \leq c_j \text{ for each } j = 1,\dots, m$$ $$x_{ij} = 0 \text{ or } 1$$

Your problem has similar structure. You have $n$ items and $m$ buyers (or knapsacks) with buying ability (or capacity). You also want to maximize the profit. The difference is that in your case capacities are equal to profits $w_{ij} = p_{ij}$, however you may have additional requirement such as not all buyers can buy all items (or not all items can be assigned to all knapsacks).

My guess is that additional requirements wouldn't make it solvable in polynomial time. So, you may try, for instance, Greedy approximation algorithm, or formulate it as an Linear (Integer) Program and solve it yet another approximation algorithm.

Answer 2

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.