pythonalgorithmmatrixhungarian-algorithm

Hungarian method with disallowed assignments and unsolvable matrices

I'm not that well-versed in the assignment problem and trying to find an alternative to Munkres/the Hungarian method that works for variations of the assignment problem where:

  1. Some assignments are disallowed
  2. It may not be possible to assign every person/row to an assignment/column (in which case, I'd just like to make as many assignments as possible- perhaps by finding and working with the largest solvable matrix)

I've been able to modify a Munkres implementation to handle #1, but it breaks down in cases like:

[  D,   D,   1,   D,   D,   D,   D,   D]
[  D,   D,   D,   D,   1,   D,   D,   D]
[  1,   D,   D,   D,   D,   1,   1,   1]
[  D,   D,   D,   D,   D,   2,   2,   2]
[  D,   1,   D,   D,   D,   3,   3,   3]
[  D,   D,   1,   2,   3,   D,   D,   D]
[  D,   D,   1,   2,   3,   D,   D,   D]
[  D,   D,   1,   2,   3,   D,   D,   D]

# ("D" = disallowed)

Eventually just can't get past:

[  D,  D,  0,  D,  D,  D,  D,  D]
[  D,  D,  D,  D,  0,  D,  D,  D]
[  0,  D,  D,  D,  D,  0,  0,  0]
[  D,  D,  D,  D,  D,  0,  0,  0]
[  D,  0,  D,  D,  D,  0,  0,  0]
[  D,  D,  0,  0,  2,  D,  D,  D]
[  D,  D,  0,  0,  2,  D,  D,  D]
[  D,  D,  0,  0,  2,  D,  D,  D]

Is there another algorithm I should be using to handle this? Or some algorithmic way to detect unsolvable cases like the one above before passing it into the algorithm (it would get rather expensive if I detected these cases by first running the algorithm each time)?

For reference, here's the code I'm working with (in Python): https://github.com/knyte/munkres/blob/master/munkres.py

Solution

  • Assuming that you're minimizing the cost of the maximum number of assignments, modify Munkres's algorithm to use pairs of numbers (a, b) with the following arithmetic and order rules:

    (a, b) + (c, d) = (a + c, b + d)
-(a, b) = (-a, -b)
(a, b) < (c, d) if and only if a < c or (a = c and b < d).

    Use (0, 0) instead of 0.

    The interpretation of a cost (a, b) is that a is the number of disallowed assignments, and b is the total cost of allowed assignments. Thus every cost c gets mapped to (0, c), and every disallowed assignment gets mapped to (1, 0).

    When you get the answer back from Munkres's algorithm, throw away all of the disallowed assignments.