Generalization of assignment problem - multiple agents required to complete tasks

Question

I have an assignment problem where each task $t_i$ requires $n_i$ agents to complete it (there are many more agents available then there are tasks for them to complete, even with multiple agents required per task). What optimization technique should I use to find the solution? Is there a non brute force solution to this?

Answer 1

Let $T$ be the set of tasks, $A$ the set of agents, $n_t$ the number of agents required for task $t$, and $c_{a,t}$ the cost of assigning agent $a$ to task $t$. Define $$ x_{a,t} = \begin{cases} 1,& \text{if agent $a$ is assigned to task $t$}\\ 0,& \text{otherwise}. \end{cases} $$ Then we can model this problem as the following integer program: \begin{align} \min\quad &\sum_{a\in A}c_{a,t}x_{a,t}\\ \mathrm{s.t.}\quad &\sum_{a\in A} x_{a,t} = n_t,\quad t\in T\\ &\sum_{t\in T} x_{a,t} \leqslant 1,\quad a\in A\\ &x_{a,t}\in\{0,1\}. \end{align}