Optimal matching between differently sized sets of agents and tasks

Question

The problem:

I have a set of agents A of size a, a set of tasks Tof size t and a profit function p(agent, task). Each agent can only be assigned one task and each task can only be handled by one agent.

I need to find a set of (agent, task) pairs for which the total profit is maximal.

I've started out with a naive solution that would recursively find the (agent, task) pair with the highest profit. The result turned out to be suboptimal. I then tried all permutations of the larger set - the program never finished. :)

I think this is some kind of assignment problem but I've so far only found solutions for linear assignment problems where the number of agents and tasks is equal.

Can you point me to an efficient algorithm for this problem or suggest an approach for this problem?

Answer 1

Much delayed, but your solution is finally here! While DasKrumelmonster is partially right in that you are trying to solve the linear assignment problem, you are specifically attempting to solve a bipartite graph.

Take a look at this GitHub repository aptly named Bipartite Solver. It not only provides you with a java implementation of the Jonker-Volgenant algorithm suggested in the other answer, there are 4 algorithms to choose from.

The first is greedy search, which is exactly what you mentioned you first implemented - it iteratively finds the best match. While it may provide a sub-optimal solution, the majority of the time it is near-optimal. It is the fastest of the bunch.

The second is brute force search. Just like you mentioned, the program takes a loooong time to do any more than a 9x9 mapping, but for small numbers, this is sufficient, and optimal.

The third is a variant of brute force, but with alpha-beta tree-pruning. You get a ~20% speed increase on average, but anything more than 13x13, you run out of memory.

The fourth is LAPJV, which is optimal and crazy fast. I mean 2000x2000 in 1s fast! This is what you should go with, hands down.

The library has a whole bunch of executables if you wish to try out the algorithms without building it from source.

This library looks like exactly what you were asking for, only a year too late. Better late than never, I guess.

Answer 2

That problem is known as "linear assignment problem".

While is is often described with two sets that have the same number of elements, that is not necessary. You can pad the matrix to a quadratic one. Also, if it is not necessary that the larger set gets completely assigned, you may want to pad the matrix further (= double each dimension).

I have done something similar, but this is a cost matrix (i.e. the dummy elements have high values) this is the original matrix K:

which is not quadratic. It is then padded with dummy values:

So that we can execute the munkres-algorithm. However, this matrix means that every element of (1,2,3,4) will get assigned, even if that assignment has a very high cost. (Element 4 in this case has a high cost and will fetch the dummy row. But if Element 3 had similar costs, then I would end up with a bad matching)

Therefore, the matrix is padded further:

This last step may not be needed in your case. If the profit cannot become negative, then any matching will be better than none, right?

---

I switched to the Jonker-Volgenant Algorithm which solves the same problem in much shorter time. (Although it might not result in the exact same results in some cases) I got it from MATLAB FileExchange which is (apparently) based upon this paper.