3
$\begingroup$

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!

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ If nobody comes up with a better algorithm you could always write an ILP and use a solver. $\endgroup$ – adrianN Sep 22 '17 at 15:15
  • $\begingroup$ So if you duplicate each task (according to the max number of agents assigned to it), this reduces to a maximum weight bipartite matching problem where the matching should touch every vertex on the left side (every agent) but need not touch every vertex on the right side (every task instance). You might want ot check if standard algorithms for maximum weight bipartite matching can be generalized to this variant. You might also look at en.wikipedia.org/wiki/Minimum-cost_flow_problem. $\endgroup$ – D.W.♦ Sep 22 '17 at 15:47
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.