The Assignment Problem, una función numpy?

Question

Dado que un assignment problem se puede representar en forma de una matriz única, estoy vagando si numpy tiene una función para resolver dicha matriz. Hasta ahora no he encontrado ninguno. ¿Quizás uno de ustedes sabe si numpy/scipy tiene una función de asignación de problemas?

Edit: Mientras tanto he encontrado una implementación de python (no numpy/scipy) en http://www.clapper.org/software/python/munkres/. Todavía supongo que una implementación numpy/scipy podría ser mucho más rápida, ¿verdad?

Answer 1

No, NumPy no contiene dicha función. La optimización combinatoria está fuera del alcance de NumPy. Puede ser posible hacerlo con uno de los optimizadores en scipy.optimize pero tengo la sensación de que las restricciones pueden no ser correctas.

NetworkX probablemente también incluya algoritmos para problemas de asignación.

Answer 2

Hay una implementación del Munkres' algorithm como un módulo de extensión de python que tiene soporte numpy. Lo he usado con éxito en mi vieja computadora portátil. Sin embargo, no funciona en mi nueva máquina, supongo que hay un problema con las versiones numpy "nuevas" (o con el arco de 64 bits).

Answer 3

Ahora existe una implementación numpy del algoritmo de munkres en scikit-learn bajo sklearn/utils/linear_assignment_.py, su única dependencia es numpy. Lo probé con algunas matrices de aproximadamente 20x20, y parece ser aproximadamente 4 veces más rápido que el que está vinculado en la pregunta. cProfiler muestra 2.517 segundos frente a 9.821 segundos para 100 iteraciones.

Answer 4

Tenía la esperanza de que la nueva scipy.optimize.linear_sum_assignment sería más rápido, pero (quizás no es sorprendente) el Cython library (que no tiene el apoyo pip) es significativamente más rápido, al menos para mi caso de uso:

$ 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 vio resultados similares para tamaños entre 2x2 y 100x120 (10-40x más rápido).

Answer 5

Otra implementación más rápida, como ya lo insinuó @Matthew: scipy.optimize tiene una función llamada linear_sum_assignment. De los documentos:

El método utilizado es el algoritmo húngaro, también conocido como el algoritmo Munkres o Kuhn-Munkres.

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