Programación de enteros mixtos: una guía para la toma de decisiones computacional

La investigación de operaciones, la ciencia del uso de computadoras para tomar decisiones óptimas, se ha utilizado y aplicado en muchas áreas del software. Para dar algunos ejemplos, las empresas de logística lo utilizan para determinar la ruta óptima para ir del punto A al punto B, las empresas de energía lo utilizan para determinar los programas de producción de energía y las empresas de fabricación lo utilizan para encontrar patrones de personal óptimos para sus fábricas.

Hoy, exploraremos el poder de la investigación de operaciones al analizar un problema hipotético. Específicamente, utilizaremos la programación de enteros mixtos (MIP) para determinar el patrón de dotación de personal óptimo para una fábrica hipotética.

Algoritmos de investigación de operaciones

Antes de sumergirnos en nuestro problema de ejemplo, es útil repasar algunos conceptos básicos en la investigación de operaciones y comprender un poco de las herramientas que usaremos hoy.

Algoritmos de programación lineal

La programación lineal es una técnica de investigación de operaciones utilizada para determinar el mejor resultado en un modelo matemático donde el objetivo y las restricciones se expresan como un sistema de ecuaciones lineales. Un ejemplo de modelo de programación lineal podría verse así:

 Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2)

En nuestro ejemplo muy simple, podemos ver que el resultado óptimo es 5, con a = 2 y b = 3. Si bien este es un ejemplo bastante trivial, probablemente puedas imaginar un modelo de programación lineal que utiliza miles de variables y cientos de restricciones. .

Un buen ejemplo podría ser un problema de cartera de inversiones, donde podría terminar con algo como lo siguiente, en pseudocódigo:

 Maximize <expected profit from all stock investments> Subject to: <investment in the technology sector must be between 10% - 20% of portfolio> <investment in the consumer staples must not exceed investment in financials> Etc. ...

Lo cual sería bastante complejo y difícil de resolver a mano o por ensayo y error. El software de investigación de operaciones utilizará varios algoritmos para resolver estos problemas rápidamente. Si está interesado en los algoritmos subyacentes, le recomiendo aprender sobre el método simplex aquí y el método del punto interior aquí.

Algoritmos de programación entera

La programación entera es como la programación lineal con una concesión adicional para que algunas o todas las variables sean valores enteros. Si bien esto puede no parecer una gran mejora al principio, nos permite resolver muchos problemas que podrían haber quedado sin resolver utilizando solo la programación lineal.

Uno de esos problemas es el problema de la mochila, en el que se nos da un conjunto de artículos con valores y pesos asignados y se nos pide que encontremos la combinación de artículos de mayor valor que podamos meter en nuestra mochila. Un modelo de programación lineal no podrá resolver esto porque no hay forma de expresar la idea de que puedes poner un artículo en tu mochila o no, pero no puedes poner parte de un artículo en tu mochila; cada variable es una variable continua. ¡variable!

Un problema de mochila de ejemplo podría tener los siguientes parámetros:

Y el modelo MIP se verá así:

 Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint)

La solución óptima, en este caso, es a=0, b=1, c=0, d=1, siendo el valor del ítem total 17.

El problema que resolveremos hoy también requerirá programación entera, ya que un empleado en una fábrica puede programar un turno o no; en aras de la simplicidad, no puede programar a un empleado para 2/3 de un turno en esta fábrica.

Para hacer posible la programación entera, se utilizan varios algoritmos matemáticos. Si está interesado en los algoritmos subyacentes, le recomiendo que estudie aquí el algoritmo de planos de corte y el algoritmo de ramificación y unión.

Problema de ejemplo: programación

Descripción del problema

Hoy exploraremos el problema de dotar de personal a una fábrica. Como gerentes de la fábrica, querremos minimizar los costos de mano de obra, pero queremos asegurar una cobertura suficiente para cada turno para satisfacer la demanda de producción.

Supongamos que tenemos cinco turnos con las siguientes demandas de personal:

Y, supongamos que tenemos los siguientes trabajadores:

Para simplificar el problema, supongamos por el momento que la disponibilidad y el costo son las únicas preocupaciones.

Nuestras Herramientas

Para el problema de hoy, usaremos una pieza de software de corte y ramificación de código abierto llamado CBC. Haremos una interfaz con este software utilizando PuLP, que es una biblioteca de modelado de investigación de operaciones popular para Python. Puedes encontrar información al respecto aquí.

PuLP nos permite construir modelos MIP de una manera muy Pythonic y se integra muy bien con el código Python existente. Esto es muy útil ya que algunas de las herramientas de análisis y manipulación de datos más populares están escritas en Python, y la mayoría de los sistemas de investigación de operaciones comerciales requieren un procesamiento de datos extenso antes y después de la optimización.

Para demostrar la simplicidad y elegancia de PuLP, aquí está el problema de la mochila anterior y resuelto en PuLP:

 import pulp as pl # declare some variables # each variable is a binary variable that is either 0 or 1 # 1 means the item will go into the knapsack a = pl.LpVariable("a", 0, 1, pl.LpInteger) b = pl.LpVariable("b", 0, 1, pl.LpInteger) c = pl.LpVariable("c", 0, 1, pl.LpInteger) d = pl.LpVariable("d", 0, 1, pl.LpInteger) # define the problem prob = pl.LpProblem("knapsack", pl.LpMaximize) # objective function - maximize value of objects in knapsack prob += 5 * a + 7 * b + 2 * c + 10 * d # constraint - weight of objects cannot exceed 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 status = prob.solve() # solve using the default solver, which is cbc print(pl.LpStatus[status]) # print the human-readable status # print the values print("a", pl.value(a)) print("b", pl.value(b)) print("c", pl.value(c)) print("d", pl.value(d))

Ejecute esto, y debería obtener el resultado:

 Optimal a 0.0 b 1.0 c 0.0 d 1.0

¡Ahora nuestro problema de programación!

Codificando nuestra solución

La codificación de nuestra solución es bastante sencilla. Primero, querremos definir nuestros datos:

 import pulp as pl import collections as cl # data shift_requirements = [1, 4, 3, 5, 2] workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } }

A continuación, querremos definir el modelo:

 # define the model: we want to minimize the cost prob = pl.LpProblem("scheduling", pl.LpMinimize) # some model variables cost = [] vars_by_shift = cl.defaultdict(list) for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%s" % (worker, shift), 0, 1, pl.LpInteger) vars_by_shift[shift].append(worker_var) cost.append(worker_var * info['cost']) # set the objective to be the sum of cost prob += sum(cost) # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum(vars_by_shift[shift]) >= requirement

¡Y ahora solo le pedimos que resuelva e imprima los resultados!

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var.name for var in vars if var.varValue == 1], }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']))

Una vez que ejecute el código, debería ver los siguientes resultados:

 Result: Optimal Shift: 0 workers: Arya_0 Shift: 1 workers: Melisandre_1, Bran_1, Theon_1, Arya_1 Shift: 2 workers: Bran_2, Jon_2, Jaime_2 Shift: 3 workers: Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3 Shift: 4 workers: Bran_4, Theon_4

Aumenta un poco la dificultad: restricciones adicionales

Aunque el modelo anterior era interesante y útil, no demuestra completamente el poder de la programación de enteros mixtos. También podríamos escribir fácilmente un ciclo for para encontrar los x trabajadores más baratos para cada turno, donde x es el número de trabajadores necesarios para un turno. Para demostrar cómo se puede usar MIP para resolver un problema que sería difícil de resolver de manera imperativa, examinemos qué sucedería si agregamos algunas restricciones adicionales.

Restricciones adicionales

Supongamos que, debido a las nuevas normas laborales, no se pueden asignar trabajadores a más de 2 turnos. Para dar cuenta del aumento de trabajo, hemos reclutado la ayuda de Dothraki Staffing Group, que suministrará hasta 10 trabajadores Dothraki para cada turno a una tarifa de $40 por turno.

Además, supongamos que, debido a algunos conflictos interpersonales en curso fuera de nuestra fábrica, Cersei y Jaime no pueden trabajar en ningún turno junto con Daenerys o Jon. Además, Jaime y Cersei no pueden trabajar juntos en ningún turno. Finalmente, Arya, que tiene relaciones interpersonales particularmente complejas, no puede trabajar en el mismo turno con Jaime, Cersei o Melisandre.

La adición de estas dos nuevas restricciones y recursos de ninguna manera hace que el problema sea irresoluble por medios imperativos, pero hace que la solución sea mucho más difícil, ya que habrá que tener en cuenta los costos de oportunidad de programar a un trabajador para un turno en particular.

Solución

Sin embargo, con la programación de enteros mixtos, es mucho más fácil. Simplemente necesitamos modificar nuestro código así:

Defina la lista de prohibición y algunas restricciones:

 ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Complete las variables para implementar las restricciones de prohibición y turno máximo:

 for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%d" % (worker, shift), 0, 1, pl.LpInteger) # store some variable data so we can implement the ban constraint var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # store vars by variable so we can implement the max shift constraint vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost'])

Agrega las variables Dothraki:

 for shift in range(len(shift_requirements)): dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger) cost.append(dothraki_var * DOTHRAKI_COST) dothrakis_by_shift[shift] = dothraki_var

También necesitaremos un bucle ligeramente modificado para calcular los requisitos de cambio y prohibición:

 # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # set the ban requirements for shift, vars in vars_by_shift.items(): for var1 in vars: for var2 in vars: worker_pair = var1[1][0], var2[1][0] if worker_pair in ban_list: prob += var1[0] + var2[0] <= 1 # set the labor standards: for worker, vars in vars_by_worker.items(): prob += sum(vars) <= 2

Y finalmente, para imprimir los resultados:

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var[1][0] for var in vars if var[0].varValue == 1], "dothrakis": dothrakis_by_shift[shift].varValue }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']), 'dothrakis hired:', int(result['dothrakis']))

Y deberíamos estar listos para irnos. Ejecute el código y debería ver el resultado como se muestra a continuación:

 Result: Optimal Shift: 0 workers: Arya dothrakis hired: 0 Shift: 1 workers: Melisandre, Theon, Tyrion, Jaime dothrakis hired: 0 Shift: 2 workers: Bran, Jon dothrakis hired: 1 Shift: 3 workers: Bran, Daenerys, Theon, Tyrion, Arya dothrakis hired: 0 Shift: 4 workers: Melisandre, Jaime dothrakis hired: 0

Y ahí lo tenemos, un resultado que respeta la lista de trabajadores prohibidos, sigue las normas laborales y utiliza juiciosamente a los trabajadores Dothraki.

Conclusión

Hoy exploramos el uso de la programación de enteros mixtos para tomar mejores decisiones. Discutimos los algoritmos y técnicas subyacentes utilizados en la investigación de operaciones y analizamos un problema de ejemplo que es representativo de cómo se usa la programación de enteros mixtos en el mundo real.

Espero que este artículo te haya inspirado a aprender más sobre la investigación de operaciones y te haya hecho pensar en cómo se puede aplicar esta tecnología a tus proyectos. Realmente solo hemos visto la punta del iceberg cuando se trata del emocionante mundo de los algoritmos de optimización y la investigación de operaciones.

Puede encontrar todo el código relacionado con este artículo en GitHub. Si desea discutir más, ¡comparta sus comentarios a continuación!