Problemas de asignación en Google OR-Tools

Tal como se ha abordado en artículos anteriores, dentro de la investigación de operaciones, el problema de asignación corresponde a una variación del problema original de transporte. Es uno de los problemas de optimización combinatoria más popularizados debido a su alto grado de aplicación práctica.

Suponga que es necesario llevar a cabo un conjunto de tareas, y que para ello se cuenta con un conjunto de operarios; además, cada trabajador en particular ejecutando una tarea en particular tiene un costo específico. Pues bien, el problema consiste en asignar a cada trabajador como máximo una tarea específica, sin que dos trabajadores puedan realizar la misma tarea, mientras se minimiza el costo total.

En el modelo de asignación, la idea fundamental de resolución es ¿Qué conjunto de fuentes satisface mejor el conjunto de destinos?

En artículos anteriores hemos planteado la resolución de problemas de asignación mediante el método húngaro (manual) y mediante programación lineal, haciendo uso de WinQSB.

El objetivo de este artículo consiste en utilizar las librerías del software Google OR-Tools para abordar un problema de asignación clásico y una variación del modelo mediante un criterio de maximización.

El problema

Con el propósito de evaluar los resultados obtenidos mediante distintos métodos y solucionadores, utilizaremos el mismo problema que abordamos mediante el método húngaro.

La compañía de manufactura «Jiménez y Asociados» desea realizar una jornada de mantenimiento preventivo a sus tres máquinas principales A, B y C. El tiempo que demanda realizar el mantenimiento de cada máquina es de 1 día, sin embargo la jornada de mantenimiento no puede durar más de un día, teniendo en cuenta que la compañía cuenta con tres proveedores de servicios de mantenimiento debe de asignarse un equipo de mantenimiento a cada máquina para poder cumplir con la realización del mantenimiento preventivo. Teniendo en cuenta que según el grado de especialización de cada equipo prestador de servicios de mantenimiento el costo de la tarea varía para cada máquina en particular, debe de asignarse el equipo correcto a la máquina indicada con el objetivo de minimizar el costo total de la jornada. Los costos asociados se pueden observar en la siguiente tabla:

Tabla 1

Resolviendo un problema de asignación mediante Google OR-Tools

De acuerdo a lo mencionado en el artículo de introducción a Google OR-Tools, esta herramienta soporta múltiples lenguajes de programación, así entonces, haremos uso del lenguaje de programación Python.

Del mismo modo, OR-Tools cuenta con un par de solucionadores para abordar problemas de asignación:

En este caso, utilizaremos el solucionador MIP.

Paso 1: Importar la librería

El siguiente fragmento de código importa las librerías necesarias:

# Importar la librería de Google OR-Tools
from ortools.linear_solver import pywraplp

Paso 2: Declarar el solucionador (MIP)

El siguiente fragmento de código declara el solucionador mediante el que se abordará el problema:

# Declarar el solucionador que abordará el modelo
solver = pywraplp.Solver.CreateSolver('SCIP')

Paso 3: Crear la data del modelo

El siguiente fragmento de código crea la data del modelo de asignación:

# Crear la data del modelo de asignación
costs = [
    [10, 9, 5],
    [9, 8, 3],
    [6, 4, 7],
]
num_teams = len(costs)
num_machines = len(costs[0])

La matriz de costos corresponde a los valores de la tabla 1 para asignar los equipos de mantenimiento a las máquinas.

El número de equipos de mantenimiento y el número de máquinas (tareas) los calcula mediante la función len  a partir de la matriz de costos. En un sentido práctico, cuenta el número de elementos de la matriz.

Paso 4: Crear las variables

El siguiente fragmento de código crea las variables binarias enteras del problema de asignación (x[i, j]):

# x[i, j] es una matriz de variables binarias 0-1, que será 1
# si un equipo de mantenimiento i es asignado a la máquina j.
x = {}
for i in range(num_teams):
    for j in range(num_machines):
        x[i, j] = solver.IntVar(0, 1, '')

Paso 5: Crear las restricciones

El siguiente fragmento de código crea las restricciones del problema de asignación:

# Cada equipo de mtto. podrá ser asignado a un máximo de una máquina
for i in range(num_teams):
    solver.Add(solver.Sum([x[i, j] for j in range(num_machines)]) <= 1)
# Cada máquina será asignada exactamente a un equipo de mantenimiento
for j in range(num_machines):
    solver.Add(solver.Sum([x[i, j] for i in range(num_teams)]) == 1)

Paso 6: Crear la función objetivo

El siguiente fragmento de código crea la función objetivo con un criterio de optimización minimizar

# Función objetivo con criterio de optimización: minimizar
objective_terms = []
for i in range(num_teams):
    for j in range(num_machines):
        objective_terms.append(costs[i][j] * x[i, j])
solver.Minimize(solver.Sum(objective_terms))

Paso 7: Invocar el solucionador

# Invoca el solucionador
status = solver.Solve()

Paso 8: Imprimir la solución

# Configura los parámetros de impresión, las salidas del modelo
if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Costo total = ', solver.Objective().Value(), '\n')
    for i in range(num_teams):
        for j in range(num_machines):
            # Test if x[i,j] is 1 (con tolerancia de punto flotante)
            if x[i, j].solution_value() > 0.5:
                print('Equipo %d asignado a la máquina %d. Costo = %d' %
                      (i, j, costs[i][j]))

Es posible que el desarrollo de los ocho pasos anteriores demande algún grado de complejidad subyacente del uso de un lenguaje de programación; sin embargo, es preciso mencionar que, el modelo anterior queda perfectamente configurado, y puede replicarse con modificaciones menores en múltiples problemas de asignación.

¿Cómo ejecutar el modelo?

Alternativa 1, ejecución en nuestro equipo:

Lo primero que debemos considerar, en el caso de que queramos ejecutar este código en nuestro equipo, es que es preciso contar con la instalación de Python en nuestro equipo de cómputo, así mismo debemos contar con la última versión del comando pip y por supuesto, el software OR-Tools. Una guía detallada de la instalación de estos requerimientos la podrás encontrar en el siguiente enlace:

Instalación de OR-Tools para Python

Ahora, lo recomendable es trabajar con algún editor de código práctico (IDE), por ejemplo: Sublime Text, o Spyder (Una herramienta más completa y por ende más robusta y pesada).

Alternativa 2, ejecución en un entorno virtual (Recomendado):

Podemos utilizar del mismo modo, un entorno virtual. En este caso recomendamos el uso de Colaboratory de Google, un entorno que cuenta con todas las herramientas necesarias para nuestros desarrollos. No tendremos que instalar nada en nuestro equipo, y aprovecharemos la potencia de las máquinas de Google.

El código completo de nuestro desarrollo lo presentamos a continuación. También puedes ver el cuaderno de este módulo en nuestro Colaboratory: Asignación.

# Importar la librería de Google OR-Tools
from ortools.linear_solver import pywraplp

# Declarar el solucionador que abordará el modelo
solver = pywraplp.Solver.CreateSolver('SCIP')

# Data del modelo
costs = [
    [10, 9, 5],
    [9, 8, 3],
    [6, 4, 7],
]
num_teams = len(costs)
num_machines = len(costs[0])

# Variables del modelo
x = {}
for i in range(num_teams):
    for j in range(num_machines):
        x[i, j] = solver.IntVar(0, 1, '')

# Restricciones del modelo
for i in range(num_teams):
    solver.Add(solver.Sum([x[i, j] for j in range(num_machines)]) <= 1)
# Cada máquina será asignada exactamente a un equipo de mantenimiento
for j in range(num_machines):
    solver.Add(solver.Sum([x[i, j] for i in range(num_teams)]) == 1)

# Función objetivo con criterio de optimización: minimizar
objective_terms = []
for i in range(num_teams):
    for j in range(num_machines):
        objective_terms.append(costs[i][j] * x[i, j])
solver.Minimize(solver.Sum(objective_terms))

# Invoca el solucionador
status = solver.Solve()

# Configura los parámetros de impresión, las salidas del modelo
if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Costo total = ', solver.Objective().Value(), '\n')
    for i in range(num_teams):
        for j in range(num_machines):
            # Test if x[i,j] is 1 (con tolerancia de punto flotante)
            if x[i, j].solution_value() > 0.5:
                print('Equipo %d asignado a la máquina %d. Costo = %d' %
                      (i, j, costs[i][j]))

Ejecutamos:

Y bien, tenemos la solución a este problema simple de asignación en menos de 1 segundo.

Podemos observar que se ha obtenido la misma respuesta que la lograda mediante el método húngaro y programación lineal (WinQSB).

Ahora bien, el modelo de asignación y el script del solucionador quedaron desarrollados en un lenguaje de programación estándar y ampliamente utilizado. Desde luego, las posibilidades de integrar datos de entrada y procesar los datos de salidas son interesantes. Por ejemplo, es posible desarrollar un script mediante el cual el código ya desarrollado tome los datos de entrada desde un archivo de Excel, o desde un servidor externo.

También, es posible desarrollar una interfaz amigable desde la cual se ingrese la información; o vincular los datos de salida con algún modelo o documento determinado.

Ahora, podemos evidenciar una de las bondades de este tipo de modelamiento, y es la flexibilidad. Pues bien, vamos a modificar muy fácilmente la información de entrada y el criterio de optimización, para desarrollar un modelo de asignación cuyo criterio sea maximizar. Para ello, vamos a abordar un problema de asignación planteado anteriormente, con el propósito de contrastar los resultados.

Modelamiento y solución de un problema de maximización mediante Google OR-Tools

El problema

Una organización de recolección de café cuenta con tres equipos de siembra y cosecha del mismo (equipos 1, 2, 3). Estos equipos de trabajo se encuentran entrenados para trabajar en condiciones particulares del proceso, condiciones como lo son el tipo de suelo, las condiciones del clima y el tipo de grano. La organización cuenta con cuatro terrenos disponibles para efectuar el proceso de siembra y cosecha (terrenos A, B, C, D), estos terrenos tienen condiciones particulares de suelo, clima y tipo de grano. Cada equipo cuenta con la capacidad de efectuar el proceso en solo uno de los terrenos disponibles, salvo el equipo 2, que cuenta con una serie de herramientas tecnológicas que le permiten realizar la siembra y cosecha del grano en dos de los terrenos disponibles.

Se ha contratado a un Ingeniero Industrial con el objetivo de realizar las asignaciones precisas que maximicen la cantidad de sacos de café cosechados en total. El siguiente tabulado muestra la capacidad (en cientos de sacos) de cosecha de café de cada uno de los equipos dependiendo de cada uno de los terrenos.

Dado que existe un equipo que cuenta con la capacidad de trabajar en dos de los terrenos disponibles (desarrollar dos tareas), renombraremos los equipos partiendo desde el 0, así mismo los terrenos, y el equipo 1 y 2 corresponderán a una misma flotilla (misma capacidad de producción) que puede desarrollar dos tareas (atender dos terrenos). Así entonces, el tabulado con las capacidades de producción se muestra a acontinuación:

Tabla 2

# Crear la data del modelo de asignación
capacidad = [
    [13, 7, 12, 12],
    [10, 13, 15, 7],
    [10, 13, 15, 7],
    [13, 10, 8, 8],
]
num_equipos = len(capacidad)
num_terrenos = len(capacidad[0])

# Función objetivo con criterio de optimización: maximizar
objective_terms = []
for i in range(num_equipos):
    for j in range(num_terrenos):
        objective_terms.append(capacidad[i][j] * x[i, j])
solver.Maximize(solver.Sum(objective_terms))

El código completo, con algunas modificaciones de acuerdo al renombre de las variables y a los textos que acompañarán los resultados se presenta a continuación (también puedes encontrarlo en nuestro Colaboratory):

# Importar la librería de Google OR-Tools
from ortools.linear_solver import pywraplp

# Declarar el solucionador que abordará el modelo
solver = pywraplp.Solver.CreateSolver('SCIP')

# Data del modelo
capacidad = [ 
[13, 7, 12, 12], 
[10, 13, 15, 7], 
[10, 13, 15, 7],
[13, 10, 8, 8], 
] 
num_equipos = len(capacidad) 
num_terrenos = len(capacidad[0])

# Variables del modelo
x = {}
for i in range(num_equipos):
    for j in range(num_terrenos):
        x[i, j] = solver.IntVar(0, 1, '')

# Restricciones del modelo
for i in range(num_equipos):
    solver.Add(solver.Sum([x[i, j] for j in range(num_terrenos)]) <= 1)

for j in range(num_terrenos):
    solver.Add(solver.Sum([x[i, j] for i in range(num_equipos)]) == 1)

# Función objetivo con criterio de optimización: maximizar
objective_terms = []
for i in range(num_equipos):
    for j in range(num_terrenos):
        objective_terms.append(capacidad[i][j] * x[i, j])
solver.Maximize(solver.Sum(objective_terms))

# Invoca el solucionador
status = solver.Solve()

# Configura los parámetros de impresión, las salidas del modelo
if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Producción total = ', solver.Objective().Value(), '\n')
    for i in range(num_equipos):
        for j in range(num_terrenos):
            # Test if x[i,j] is 1 (con tolerancia de punto flotante)
            if x[i, j].solution_value() > 0.5:
                print('Equipo %d asignado al terreno %d. Producción = %d' %
                      (i, j, capacidad[i][j]))