Le problème d'affectation, une fonction numpy?

Question

Puisqu'un assignment problem peut être posé sous la forme d'une seule matrice, je suis errant si numpy a une fonction pour résoudre une telle matrice. Jusqu'à présent, je n'en ai trouvé aucun. Peut-être que l'un d'entre vous sait si Numpy/Scipy a une fonction d'assignation-résolution de problèmes?

Modifier: En attendant, j'ai trouvé une implémentation python (pas numpy/scipy) à http://www.clapper.org/software/python/munkres/. Pourtant, je suppose qu'une mise en œuvre numpy/scipy pourrait être beaucoup plus rapide, non?

Answer 1

Non, NumPy ne contient pas une telle fonction. L'optimisation combinatoire est en dehors de la portée de NumPy. Il peut être possible de le faire avec l'un des optimiseurs dans scipy.optimize mais j'ai le sentiment que les contraintes peuvent ne pas être de la bonne forme. Probablement aussi des algorithmes pour les problèmes d'affectation.

Answer 2

Il existe une implémentation du Munkres' algorithm en tant que module d'extension python qui prend en charge numpy. Je l'ai utilisé avec succès sur mon vieux portable. Cependant, cela ne fonctionne pas sur ma nouvelle machine - je suppose qu'il y a un problème avec les "nouvelles" versions numpy (ou archite 64bit).

Answer 3

Il existe maintenant une implémentation numpy de l'algorithme munkres dans scikit-learn sous sklearn/utils/linear_assignment_.py sa seule dépendance est numpy. Je l'ai essayé avec des matrices d'environ 20x20, et il semble être environ 4 fois plus rapide que celui associé à la question. cProfiler affiche 2,517 secondes contre 9,821 secondes pour 100 itérations.

Answer 4

J'espérais que la nouvelle scipy.optimize.linear_sum_assignment serait plus rapide, mais (peut-être sans surprise) le Cython library (qui ne prend pas en charge pip) est nettement plus rapide, au moins pour mon cas d'utilisation:

$ 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)' 
100 loops, best of 3: 3.43 msec per loop 
$ python -m timeit -s 'from munkres import munkres; import numpy as np; np.random.seed(0); c = np.random.rand(20,30)' 'a = munkres(c)' 
10000 loops, best of 3: 139 usec 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)' 
100 loops, best of 3: 3.01 msec per loop 
$ python -m timeit -s 'from munkres import munkres; import numpy as np; np.random.seed(0)' 'c = np.random.rand(20,30); a = munkres(c)' 
10000 loops, best of 3: 127 usec per loop 

I vu des résultats similaires pour les tailles entre 2x2 et 100x120 (10-40x plus rapide).

Answer 5

Encore une autre implémentation rapide, comme déjà suggéré par @Matthew: scipy.optimize a une fonction appelée linear_sum_assignment. D'après les docs:

La méthode utilisée est l'algorithme hongrois, également connu sous le nom d'algorithme de Munkres ou Kuhn-Munkres.

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