infinite loop, flips between step 4 and step 6

[emjabs]

I'm using a lot of DISALLOWED elements, so I'm not sure if that's the issue. I've provided the cost matrix I've generated.

test.txt

It's unsolvable but I doubt that should result in an infinite loop, no? I'd like to be able to return "this was unsolvable" so I can tinker with the constraints in real time.

[emjabs]

Another cost matrix that exhibits the infinite loop between steps 4 and 6...

test.txt

[Karpisek]

same problem with this matrix:
[D, 161., D],
[D, 1., D],
[D, 157., D],
[37., D, 5.],

where D stands for DISALLOWED. It ends up in infinite loop

[Karpisek]

well, Python 3 has no limit on int value, so maybe setting the DISALLOWED to just a "really high" number would do the trick. Anyway it is not "good practise" at all

[bmc]

I'm utterly swamped at the moment. I will gladly take a pull request from someone who wants to have a go at fixing the issue.

[Karpisek]

@bmc now I'm working on my bachelor thesis, so I have no much time left to look deeply into the code. Now I'll test the workaround I mentioned earlier ^^. But I'll put it to my TODO list and hopefully, I'm going to be able to solve it later on :)

anyway, thanks for the reply.

[Zoidmania]

I've run into this problem too, using v1.1.4 of the package.

I'm thinking that the following catches the edge condition:

def __check_unsolvability(matrix):
    """Checks additional conditions to see if an input Munkres cost matrix is unsolvable.

    Munkres v1.1.4 suffers from an infinite loop given some edge conditions, when it should,
    instead, emit a ``munkres.UnsolvableMatrix`` error. This function attempts to identify those
    conditions.

    Args:
        matrix (list): of lists of numbers, representing a cost matrix (or a profit matrix) suitable
            for Munkres optimization.

    Raises:
        munkres.UnsolvableMatrix: if the matrix is unsolvable.
    """

    from munkres import DISALLOWED
    from munkres import UnsolvableMatrix

    non_disallowed_indices = [] # (in possibly-offending rows)

    for row in matrix:

        ## check to see if all but 1 cell in the row are DISALLOWED

        indices = [i for i in range(len(row)) if type(row[i]) != type(DISALLOWED)]

        if len(indices) == 1:

            if indices[0] in non_disallowed_indices:
                raise UnsolvableMatrix(
                    "Encountered edge condition that the Munkres library doesn't check for!"
                )

            non_disallowed_indices.append(indices[0])

# ...

try:
    __check_unsolvability(matrix)
    index_pairs = Munkres().compute(matrix)
except UnsolvableMatrix:
    pass # handle as needed

My logic is this: if there exists more than 1 row where all of the values are DISALLOWED except for one, and the one non-DISALLOWED value has the same index in at least two of those rows, then it's unsolvable. I don't know if the same is true column-wise. I may try that as well, if I run into similar problems with columns. If I do, I could simply transpose the matrix and recurse once. Maybe.

I'm new to this algorithm though, so if I've misinterpreted something, let me know.

[jonodrew]

If nobody's picked this up yet, I'll raise a PR today, as the solution above seems to work

[jonodrew]

@emjabs do you remember what software you used to output those example text files? I want to convert them back to lists to use as test cases

[ahrnbom]

For others with the same issue, I found that using scipy.optimize.linear_sum_assignment (see here: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html) as a replacement for the munkres library works well, and solves this issue. It raises a ValueError instead of an infinite loop if the matrix is infeasible to solve.

For me, at least, it was very straightforward to switch from munkres to scipy's implementation.