The Assignment Problem, a NumPy function?

Question

Since an assignment problem can be posed in the form of a single matrix, I am wondering if NumPy has a function to solve such a matrix. So far I have found none. Maybe one of you guys know if NumPy/SciPy has an assignment-problem-solve function?

Edit: In the meanwhile I have found a Python (not NumPy/SciPy) implementation at http://software.clapper.org/munkres/. Still I suppose a NumPy/SciPy implementation could be much faster, right?

Answer 1

There is now a numpy implementation of the munkres algorithm in scikit-learn under sklearn/utils/linear_assignment_.py its only dependency is numpy. I tried it with some approximately 20x20 matrices, and it seems to be about 4 times as fast as the one linked to in the question. cProfiler shows 2.517 seconds vs 9.821 seconds for 100 iterations.

Answer 2

I was hoping that the newer scipy.optimize.linear_sum_assignment would be fastest, but (perhaps not surprisingly) the Cython library (which does not have pip support) is significantly faster, at least for my use case:

UPDATE: using munkres v1.1.2 and scipy v1.5.0 achieves the following results:

$ python -m timeit -s "from scipy.optimize import linear_sum_assignment; import numpy as np; np.random.seed(0); c = np.random.rand(20,30)" "a,b = linear_sum_assignment(c)"
10000 loops, best of 5: 32.8 usec per loop
$ python -m timeit -s "from munkres import Munkres; import numpy as np;  np.random.seed(0); c = np.random.rand(20,30); m = Munkres()" "a = m.compute(c)"
100 loops, best of 5: 2.41 msec per loop
$ python -m timeit -s "from scipy.optimize import linear_sum_assignment; import numpy as np; np.random.seed(0);" "c = np.random.rand(20,30); a,b = linear_sum_assignment(c)"
5000 loops, best of 5: 51.7 usec per loop
$ python -m timeit -s "from munkres import Munkres; import numpy as np;  np.random.seed(0)" "c = np.random.rand(20,30); m = Munkres(); a = m.compute(c)"
10 loops, best of : 26 msec per loop