Geek Answers Handbook

Custom Munkres Algorithm Problems

I have a variation on the assignment problem that the usual Munkres / Hungarian algorithm seems poorly prepared for the solution.

In the traditional assignment task, there are n workers who need to assign n tasks, and a matrix that contains the costs of assigning each worker to each task.

In this option, we have only m (m <n) employees. Since the Munkres algorithm requires an equal number of jobs and jobs, we create (n - m) "dummy" workers who can be assigned spares. In addition, the tasks themselves are organized in a large number of discrete categories.

We would like to impose a restriction on the fact that at least 1 task from each category is assigned to a real (non-financial) employee. This is difficult to do elegantly: for example, you can choose a random job from each category and artificially blow off every cost associated with a real employee, but this is a very rude decision that seriously violates the integrity of the final assignment.

Currently, we run the algorithm several times, each time evaluating the purpose of the output and then changing the cost matrix so that the costs of all tasks in any categories that were assigned only to dummies are slightly reduced. This works adequately, but for moderately large data sets (n ~ = 500), the process may take some time (each Munkres assignment takes perhaps 10 seconds to calculate, and with sufficient categories there may be a non-trivial number of iterations).

Is there a modified Munkres algorithm or a completely different algorithm that will more effectively solve this problem?

+5
source share
1 answer

Are the categories disjoint? Does each work have exactly one category? Then, what about the minimum 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

:

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

1, , ( ).

+1

More articles:


All Articles