How to solve assignment problem with additional constraints?

Question

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?

Answer 1

You can create additional "group agents" that represent combinations of actual agents (for instance, $P_{17}$ might be the pairing of $P_1$ and $P_2$) and/or additional "combo tasks" that are combinations of original tasks (for instance, $T_{9}$ might be $T_1$ and $T_3$ done together). You then assign "agents" to "tasks" using binary variables, and add constraints that preclude assigning a "group agent" to a task and also assigning one of the group's members (or another group sharing a member) to a different task, as well as constraints preventing an individual task and a "combo task" including that task (or two "combo tasks" that intersect) from being assigned simultaneously. This can be modeled as a binary integer program and solved by branch-and-bound/branch-and-cut.

Answer 2

This sounds like a special case of the parallel assignment problem in which the preemption (this is a standard notation in the scheduling theory) would be allowed. I am not aware of how this problem can still be solved by the Hungarian algorithm in an efficient way, but there are some algorithms to tackle such a problem, like $\text{LRPT}$, Longest Remaining Processing Time first. Also, another approach to solving this problem is Linear programming.