The Assignment Problem, a NumPy function?
Solution 1
No, NumPy contains no such function. Combinatorial optimization is outside of NumPy's scope. It may be possible to do it with one of the optimizers in scipy.optimize
but I have a feeling that the constraints may not be of the right form.
NetworkX probably also includes algorithms for assignment problems.
Solution 2
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.
Solution 3
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
Solution 4
Yet another fast implementation, as already hinted by @Matthew: scipy.optimize
has a function called linear_sum_assignment
. From the docs:
The method used is the Hungarian algorithm, also known as the Munkres or Kuhn-Munkres algorithm.
Solution 5
As of version 2.4 (released 2019-10-16), NetworkX solves the problem through nx.algorithms.bipartite.minimum_weight_full_matching
. At the time of writing, the implementation uses SciPy's scipy.optimize.linear_sum_assignment
under the hood, so expect the same performance characteristics.
Paul
Me likes elegant algorithms , and also a bit of Python, numpy, scipy, PIL Javascript, jQuery XSL/XSLT
Updated on June 07, 2022Comments
-
Paul over 1 year
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?