Munkres algorithm issues for non-standard assignment

Question

I have a variation of the assignment problem that the usual Munkres/Hungarian algorithm seems ill-equipped to solve.

In the traditional assignment problem, there are n workers who need to be assigned to n jobs, and a matrix that contains the cost of assigning each worker to each job.

In this variation, we have only m (m < n) workers. As the Munkres algorithm requires an equal number of workers and jobs we create (n - m) "dummy" workers who can be assigned to the spare jobs. Additionally, the jobs themselves are organised in a large number of discrete categories.

We would like to impose the constraint that at least 1 job from each category is assigned to a real (non-dummy) worker. This is difficult to do elegantly: you can for example pick a random job from each category and artifically deflate each real-worker associated cost, but this is a very crude solution that severely compromises the integrity of the final assignment.

What we do currently is run the algorithm multiple times, each time evaluating the output assignment and then modifying the cost matrix such that the costs for all jobs in any categories that were assigned only dummy workers are reduced slightly. This works adequately, but for moderately large data sets (n ~= 500) the process can take a while (each Munkres assignment takes perhaps 10 seconds to compute, and with sufficient categories there can be a non-trivial number of iterations).

Is there a modified Munkres algorithm, or a different algorithm entirely, that will solve this problem more efficiently?

Answer 1

Are categories disjoint? Each job has exactly one category? Then, How about minimum cost flow?

Node types:

SRC - source
SNK - sink
C - a node or each category
J - a node for each job
W - a node for each worker

the connections:

1) from SRC to C, capacity 1, cost 0
2) from SRC to C, capacity infinite, cost a high number
3) from C to J, capacity 1, cost 0
4) from J to W, capcity 1, the cost of job J done by worker W
5) from W to SNK, cost 0, capacity 1

Then the algorithm will fill links of type 1 first, which means each category will get at least one worker (if possible).