Algorithm for a modified worker-task assignment problem with groups of tasks and substitutability between tasks within groups

Question

I'm looking for an algorithm to solve a modified version of the assignment problem. It differs from the standard assignment problem in that the modified version has groups of tasks instead of just tasks. Similarly to the standard problem, each of the n workers is assigned one task, and there are n groups of tasks; but in this modified version no two workers can assigned tasks that are in the same group, so there are certain constraints to the assignment. (The assignment is done in order to optimize an objective, i.e., minimize overall costs or maximize overall gains.)

To be more concrete, suppose we have 3 different workers, workers 1, 2, and 3, and six different tasks, tasks a, b, m, n, x, and y, where tasks a can substitute (or be substituted by) task b, and the same relation holds between tasks m and n and between x and y. In this problem, tasks can be said to belong to the set {{a, b}, {m, n}, {x, y}}, and a worker must perform one task in {a, b} or in {m, n} or in {x, y} and no other worker will perform another task in the same group. As a result of the algorithm, if, for instance, worker 1 is assigned to task a, then worker 2 and 3 could not be assigned to task b.

I tried to find an algorithm for this problem, but I haven't succeeded since I'm not familiar with these problems. I know that if had just one task in each group of tasks, I could use an implementation of the Hungarian algorithm to solve the problem. And I also found out that if there were more tasks than workers, I could use some implementation of the minimum-cost flow problem as long as there was no groups of tasks. I think that my lack of knowledge about this kind of problems prevents me from finding the appropriate algorithm by its name. (I intend to use the algorithm with some data that I'm working on. Once I know the name of the algorithm, I'll try to find an implementation of it in some data analysis software.)

What is the name of the algorithm used for solving the problem that I described above? (It would be even better if the algorithm that solves the problem allows for a varying number of tasks within groups and for more tasks than workers. The constraint then would be that no two tasks in the same groups are assigned to workers and each worker is assigned to one task.)

Answer 1

You can solve this problem as follows. Build a bipartite graph with one vertex per worker and one vertex per group of tasks (one vertex for the entire group; not one vertex per task). The cost of assigning worker $w$ to group $g$ is the smallest cost of assigning $w$ to some task in $g$ (i.e., for each task $t$ in $g$, look up the cost of assigning $w$ to $t$, and then take the lowest of all of those costs).

Next, solve the assignment problem in this graph. This assigns each worker to (at most) one group of tasks, and each group to (at most) one worker.

Finally, convert this into an assignment to tasks. For each worker $w$, if they are assigned to group $g$, find the lowest-cost task $t$ in $g$ (using the same procedure as above) and assign $w$ to $t$.

This will give the optimal solution to your problem.