Assignment Problem - multiple tasks, but only one chosen based on their preference (cost)

Question

I've looked at Hungarian algorithm and Knapsack problems and neither quite hit the nail on the head. I've been trying to best rephrase my question while searching for answers and haven't got anywhere.

I have agents j and tasks i. Each agent can have between 1 and 4 task preferences (each with the cost 0-3), but must have only one task assigned by the end.

Each task also has a maximum number of agents that can be assigned to it (depending on the task).

Is there an algorithm out there that will minimise the overall cost, while maximising the amount of agents assigned to each task?

I hope that's clear, never really done this sort of thing before!

Answer 1

This can be reduced to minimum-cost flow, for which there are polynomial-time algorithms.

Build a bipartite graph, with one vertex on the left for each agent, and one vertex on the right for each instance of a task. Tasks are duplicated according to the maximum number of agents they can be assigned to. For example, if task $i$ can be assigned up to 5 agents, then there will be 5 vertices on the right corresponding to task $i$. If agent $i$ has a cost of $c_{i,j}$ for task $j$, add an edge of cost $c_{i,j}$ and capacity 1 from the vertex for agent $i$ to each vertex for task $j$.

Also, add a source vertex and an edge of cost 0 and capacity 1 from the source to each left vertex; and add a sink vertex and an edge of cost 0 and capacity 1 from each right vertex to the sink. Now, find the minimum-cost flow that sends at least $n$ units of flow from the source to the sink, where $n$ is the number of agents. That will be the solution to your problem.

There are many algorithms for solving minimum-cost flow problems, and even some off-the-shelf tools. See Wikipedia for some references that will get you started to learn more.