Uno de los problemas de optimización combinatoria más conocidos es el problema de asignación. Por ejemplo, supongamos que un grupo de trabajadores necesita realizar un conjunto de tareas y que hay un costo por asignar el trabajador a cada tarea. El problema es asignar a cada trabajador como máximo una tarea, sin que dos trabajadores realicen la misma tarea, y, al mismo tiempo, se minimiza el costo total.
Puedes visualizar este problema en el siguiente gráfico, en el que hay cuatro trabajadores y cuatro tareas. Los perímetros representan todas las formas posibles de asignar trabajadores a tareas. Las etiquetas en los perímetros indican los costos de asignar trabajadores a las tareas.
Una asignación corresponde a un subconjunto de bordes, en el que cada trabajador tiene como máximo un borde que sale y no hay dos trabajadores que tengan bordes que dirijan a la misma tarea. A continuación, se muestra una posible tarea.
El costo total de la asignación es de 70 + 55 + 95 + 45 = 265.
En la siguiente sección, se muestra cómo resolver un problema de asignación usando el solucionador de MIP y el solucionador de problemas CP-SAT.
Otras herramientas para resolver problemas de tareas
Las herramientas OR también proporcionan algunas otras herramientas para resolver problemas de tareas, que pueden ser más rápidas que las soluciones MIP o CP:
- Resolutor de asignaciones de suma lineal
- Solución de problemas relacionados con el flujo de costo mínimo
Sin embargo, estas herramientas solo pueden resolver tipos simples de problemas de asignación. Por lo tanto, en el caso de los solucionadores generales que pueden manejar una amplia variedad de problemas (y son lo suficientemente rápidos para la mayoría de las aplicaciones), recomendamos los solucionadores MIP y CP-SAT.