# How to solve assignment problem with additional constraints?

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?

• Welcome to ORSE. Would you please, is it a homework training? May 16 at 7:37
• The problem specifies that you are maximizing cost. Is this a government operation?
– prubin
May 16 at 15:02
• Actually, it will be minimized the cost but I have negated the cost, so it becomes maximized. May 17 at 1:48

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.
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.