The Assignment Problem, a NumPy function?

11,863

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.

https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html

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.

Share:
11,863
Paul
Author by

Paul

Me likes elegant algorithms , and also a bit of Python, numpy, scipy, PIL Javascript, jQuery XSL/XSLT

Updated on June 07, 2022

Comments

  • Paul
    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?