Assignment problem for multiple days

Question

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.

Answer 1

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.