10
$\begingroup$

I have a problem that can be reduced to an assignment problem. (In a previous question i found out how to do that.)

Which means we have a set $A$ of agents and a set $T$ of tasks as well as a cost function $c(i,j)$. We need to find an assignment so that the total cost is minimal.

The hungarian algorithm can find an optimal solution in at least $O(n^4)$. Which sounds good to me.

My new Problem is: There is a given number of days. I have to solve the assignment problem for each day so that every task is done every day and no agent does the same task twice.

What I have tried: We could run the hungarian algorithm separately for each day and limit the number of possible combinations based on the result of the previous day. But this would get us into trouble at some of the later days, where most likely it will be impossible to find a feasibly solution.

Another idea is to somehow integrate local search to change decisions made at a previous day. But I think we can't rely on this.

The problem instances I have to face will be somewhere around $|A| = |T| = 500$. The cost matrix $C(i,j)$ will have lots of same values (E.g. mostly 1 or infinity, only some 2 or 3). So during the hungarian algorithm there is a lot of space to create different optimal solutions for a single day.

I'd be glad to hear some ideas or advises how to find a good solution for the problem. Thanks in advance.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ This is a great question! I'd suggest using min-cost flow, Hall's marriage theorem, and maximum bipartite matching. $\endgroup$ – Peter Shor Oct 21 '12 at 11:06
6
$\begingroup$

There's a way to this in polynomial time. I'll sketch the algorithm (in reverse order ... do step 2 first and step 1 second).

  1. if we can find a set of $nk$ agent-task pairs $(i,j)$ such that each task is in exactly $k$ pairs, each agent is in exactly $k$ pairs, and no pair appears more than once, then we can find $k$ assignments that together cover these $nk$ agent-task pairs. We do this by repeatedly using a maximum bipartite matching algorithm to find a perfect matching in the corresponding bipartite graph, and removing that assignment from the graph. Hall's marriage theorem guarantees we can do this.

  2. We can find the minimum-cost set of $nk$ agent-task pairs as in step 1 by using min-cost flow. Consider a network with a source $s$, a sink $t$, and nodes for each of the agents and each of the tasks. Connect the source to each agent with an edge of capacity $k$ and cost $0$. Connect each task to the sink with an edge of capacity $k$ and cost $0$. Now, connect agent $i$ to task $j$ with an edge of capacity $1$ and cost $c(i,j)$. The minimum-cost flow in this network is guaranteed to be integral (because all capacities are integral, and there is a theorem saying that this implies that there is an optimal integral min-cost flow), so the flow on each agent-task edge is $0$ or $1$. The edges $(i,j)$ with flow $1$ form the set of pairs in step 1.

There are lots of algorithms that can solve min-cost flow; it's a special case of linear programming. For your size problem, the algorithm I sketch should not just be polynomial-time, but also practical.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ One last question: The min-cost flow algorithm in step 2 (I chose cycle canceling for a start) provides an optimal solution. The maximum matching algorithm in step 1 does that to. Does this necessarily mean the whole solution is optimal? Because, my guess was that the problem is NP-Complete. $\endgroup$ – Patrick Schmidt Oct 22 '12 at 15:29
  • 1
    $\begingroup$ The whole solution is optimal. This would be a good question to assign in a combinatorial optimization course, because it's somewhat surprising you can do it. $\endgroup$ – Peter Shor Oct 23 '12 at 1:05

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.