The assignment problem is defined as:
Let there be n agents and m tasks. Any agent can be assigned to perform any task, incurring some costs that may vary depending on the agent-task assignment. We can assign at most one task for one person and at most one person for one task in such a way that the total cost of the assignment is maximized.
The Hungarian algorithm can solve this problem.
Question:
For example, I have a cost matrix as below:
T1 T2 T3 P1 2 2 2 P2 3 1 4
$T_{i}$ is the $i_{th}$ task, $P_{i}$ is the $i_{th}$ person.
The number in the row $P_{i}$ and col $T_{i}$ is the cost when assigning task $T_{i}$ to person $P_{i}$.
One solution for the above problem is: $P_1 - T1, P_2 - T_3$, the max cost is 2 + 4 = 6.
I want to add some constraints like:
Some people can do a task together (e.g: $P_1$ and $P_2$ can do task $T1$ together with a cost of 10)
Some people can do some tasks together (e.g: $P_1$ and $P_2$ can do task $T1$ and $T2$ together with a cost of 10)
A person can do some tasks (e.g: $P_1$ can do task $T1$ and $T2$ consequently with a cost of 10)
So, the new solution for the above problem is: $P1,P2-T1,T2$, the max cost is 10
How to approach solving this problem?