CODEWITHSUNDEEP
pythonalgorithmmatrixhungarian-algorithm
knyte
knyte

Reputation: 3

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

Upvotes: 0

Views: 833

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65437

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.

Upvotes: 1

Related Questions