Generación de columnas en programación lineal y el problema de corte de stock.

Column generation in linear programming and the cutting stock problem.

Cómo resolver problemas lineales con un gran número de variables de decisión ilustrado con un ejemplo de Python

Foto de Jean Vella en Unsplash

Algunos problemas de Programación Lineal (PL) que surgen de problemas combinatorios se vuelven intratables debido al gran número de variables involucradas (Gilmore & Gomory, 1961). En tales problemas, la generación de columna retrasada es una alternativa potencial de solución ya que no incluye todas las posibles variables de decisión en el problema desde el principio. Una aplicación clásica es el problema de corte de stock, en el que uno debe decidir cómo cortar un rollo de un ancho dado en piezas más pequeñas para satisfacer las demandas de tamaños de corte determinados.

A lo largo de este artículo, se presentarán algunos de los principales aspectos teóricos de la generación de columnas y se ilustrarán con el problema de corte de stock unidimensional. En la solución, se utilizará la biblioteca de Python scipy. Aquellos interesados también pueden encontrar el código completo en este repositorio de git.

En caso de que aún no esté familiarizado con la Programación Lineal, es posible que tenga una mejor comprensión de este artículo después de leer mi introducción anterior sobre el tema.

Programación lineal: Teoría y aplicaciones

Conceptos principales de optimización lineal e implementación en Python

towardsdatascience.com

Si está listo para conceptos más profundos junto con un ejemplo práctico, ¡bienvenido a bordo!

Generación de columnas: una visión general

Cuando se utiliza la generación de columnas retrasada para resolver un PL, en cada iteración se considera un problema con solo un subconjunto de columnas. Se llama Problema Maestro Restringido (RMP). En cada iteración, se resuelve el RMP y se obtiene su vector correspondiente de variables de decisión duales óptimas π. Luego, el algoritmo utiliza este resultado para resolver el subproblema o problema de precios , que tiene como objetivo encontrar nuevas variables de decisión con costos reducidos negativos. Recordemos una definición de costos reducidos.

Para cualquier variable no básica, el costo reducido para la variable es la cantidad en la que debe mejorarse el coeficiente de la función objetivo de la variable no básica antes de que esa variable se convierta en una variable básica en alguna solución óptima del PL. Winston & Goldberg (2004)

Por lo tanto, al incluir variables con costos reducidos negativos, podríamos esperar contribuciones marginales para mejorar el valor objetivo. Recuerde la interpretación económica de las variables duales como costos sombra . Una nueva variable podría potencialmente resultar en ahorros proporcionales a su contribución para cumplir las restricciones dadas sus duales correspondientes mientras aumenta el costo general por su coeficiente de costo.

Al resolver el subproblema , identificamos un conjunto S de columnas con el costo reducido más bajo dado los costos duales. Si no se identifica ninguna columna con costos reducidos negativos, detenemos el proceso ya que π es una solución dual óptima al problema original, y junto con la solución primal óptima del RMP, tenemos un par primal/dual óptimo. De lo contrario, agregamos columnas en S al RMP y repetimos (Klabjan, 2005). Este proceso se representa en la figura a continuación.

Esquema de generación de columnas. (Imagen del autor)

Observe que el subproblema es específico del problema y, en algunas situaciones, puede ser bastante costoso computacionalmente para ser formulado como un problema de programación mixta entera. Puede ser útil considerar enfoques heurísticos y/o de programación dinámica que puedan devolver, en cada iteración, más de una columna con costos reducidos negativos. En el caso de los problemas de enrutamiento de vehículos, a menudo el subproblema es un problema de camino más corto restringido. Aquellos interesados en una inmersión más profunda pueden consultar a Irnich & Desaulniers (2005) para obtener una idea de las técnicas de solución.

Recuerde ahora que el enfoque de generación de columnas retrasada presentado resuelve un problema de Programación Lineal con variables de decisión de valor real. Con el objetivo de resolver programas enteros o mixtos enteros grandes, uno podría recurrir a algunas heurísticas después de resolver la relajación o Branch & Price para imponer restricciones de integralidad. En este último enfoque, se deben considerar no solo aquellas columnas que se han generado en la solución del PL inicial, sino también generar nuevas columnas durante la solución de PL a lo largo del árbol. Una discusión más profunda sobre Branch & Price es presentada por Barnhart et al. (1998). Los autores examinan problemas comunes, estudios de casos e ideas interesantes sobre las reglas de ramificación.

El Problema de Corte de Stock

Consideremos que tenemos un conjunto de demandas I, cada una para una cantidad d de piezas de ancho w. Además, consideremos que tenemos un rollo de ancho W del cual se producirán los cortes. El conjunto de patrones de corte conocidos se denotará como P. Cada pieza de un patrón de corte p consume una unidad del rollo (c = 1) y produce aᵢₚ unidades de ancho wᵢ. Nuestro objetivo es determinar la cantidad de cortes x de cada patrón p que deben ser utilizados para cumplir con las demandas minimizando la cantidad de unidades consumidas. Podemos formular este problema de la siguiente manera.

Problema de corte de stock como un problema de cobertura de conjuntos. (Imagen por el autor).

Las variables de decisión duales asociadas con las restricciones de demanda π se utilizan luego en el problema de precios (subproblema) para encontrar nuevos patrones con costos reducidos negativos. En el caso del problema de corte de stock, debemos encontrar un nuevo patrón combinando piezas de diferentes anchos que encajen en el ancho total W y, ayudando a cumplir con las demandas de material, llevaría a más ahorros que costos nuevos. Este es un problema de mochila, que puede formularse como sigue.

Problema de precios de corte de stock. (Imagen por el autor).

En el que yᵢ corresponde al número de piezas de ancho wᵢ producidas en el nuevo patrón de corte.

Como sabemos que cada nuevo patrón tendría un costo unitario c de 1, podemos calcular el costo reducido del nuevo patrón por:

Costo reducido del nuevo patrón de corte. (Imagen por el autor).

Lo cual, en el caso de valores no negativos, debería detener el algoritmo de generación de columnas.

Para obtener soluciones enteras al problema de corte de stock, un método heurístico simple es simplemente redondear hacia arriba los valores fraccionarios obtenidos en la relajación lineal. Alternativamente, también se podría resolver el problema lineal con el conjunto de patrones producidos en la relajación lineal imponiendo restricciones de integralidad. Utilizaremos ambas estrategias en este artículo. Para instancias en las que la relajación lineal está cerca del modelo entero completo, estas estrategias pueden tener mucho éxito. Algunas diferencias pueden surgir en otras instancias en las que el número de demandas para cada patrón es relativamente pequeño.

Si uno tiene como objetivo obtener soluciones enteras exactas, Branch & Price puede ser una buena alternativa. En este enfoque, después de la ramificación en algunas de las variables iniciales, pueden incluirse nuevas columnas con costos reducidos en el nodo actual. Aquellos interesados ​​en más detalles pueden referirse a Carvalho (1998) y a Vance (1998).

¡Ahora pongámonos manos a la obra!

Solución

Comencemos la implementación de Python del problema de corte de stock, en el que se resuelve la relajación LP a la optimalidad y se resuelve un modelo entero con los patrones producidos hasta ahora. Usaremos numpy para hacer operaciones de álgebra lineal, pandas para trabajar con dataframes, scipy para los algoritmos de optimización y matplotlib para visualizar los patrones de corte en una gráfica.

import numpy as npimport pandas as pdfrom scipy.optimize import linprogimport matplotlib.pyplot as plt

Importemos un conjunto de datos que es una versión modificada del problema propuesto en la documentación de JuMP.

dataset = pd.read_csv("data.txt", sep=" ")

Y definamos los parámetros del problema.

# Ancho totalW = 100.0# Ancho y cantidad asociados con cada demandaw = dataset.w.valuesd = dataset.d.values# Parámetros A del LP para la relajación linealA = np.eye(dataset.shape[0]) * (W // w)c = np.ones_like(w)

Observemos que para inicializar la matriz A, introduje patrones de corte simples que producen el número máximo factible de rollos para cada ancho a partir de las demandas. Supongamos que hay alguna demanda de rollos de ancho 24. Esto conduciría a un patrón de corte inicial con un coeficiente de 4 dado el ancho total W de 100.

Ahora definamos una función para resolver el subproblema dado el ancho total W, un vector de anchos asociados con cada demanda w y el vector actual de variables duales duals.

def solve_knapsack(W, w, duals):    return linprog(        -duals, A_ub=np.atleast_2d(w), b_ub=np.atleast_1d(W),        bounds=(0, np.inf), integrality=1,    )

En el bucle principal, para cada solución al problema maestro restringido, usaremos la función linprog de scipy. La matriz A así como el vector de demandas se pasan como negativos por convención, ya que scipy considera solo desigualdades “menores o iguales a”.

linprog(c, A_ub=-A, b_ub=-d, bounds=(0, None))

La solución debe tener los negativos de las variables duales asociadas con las demandas almacenadas en el atributo ineqlin.marginals.

Explorando conceptos de dualidad, también se podrían obtener variables duales resolviendo el siguiente LP.

linprog(-d, A_ub=A.T, b_ub=c, bounds=(0, None))

Y pongámoslo todo junto en el bucle principal.

# Soluciones inicialessol = linprog(c, A_ub=-A, b_ub=-d, bounds=(0, None))sol_dual = linprog(-d, A_ub=A.T, b_ub=c, bounds=(0, None))diff = np.abs(sol_dual.x + sol.ineqlin.marginals).sum()print(f"Diferencia de dualidad: {diff}")# Iterarfor _ in range(1000):    duals = -sol.ineqlin.marginals    price_sol = solve_knapsack(W, w, duals)    y = price_sol.x    if 1 + price_sol.fun < -1e-4:        print(f"Iteración: {_}; Costo reducido: {(1 + price_sol.fun):.3f}")        A = np.hstack((A, y.reshape((-1, 1))))        c = np.append(c, 1)        sol = linprog(c, A_ub=-A, b_ub=-d, bounds=(0, None))    else:        break

Al final, intentemos redondear la solución de la relajación lineal y obtener la solución entera considerando solo las columnas producidas en el LP.

sol_round = linprog(c, A_ub=-A, b_ub=-d, bounds=(0, np.inf), integrality=0)print(f"Solución redondeada {np.ceil(sol_round.x).sum()}")sol = linprog(c, A_ub=-A, b_ub=-d, bounds=(0, np.inf), integrality=1)print(f"Solución entera: {sol.x.sum()}")

Lo que debería devolver:

  • Solución redondeada 339.0
  • Solución entera: 334.0

En este caso, podríamos mejorar el resultado en casi un 2% solo imponiendo restricciones de integralidad al LP en lugar de simplemente redondear la relajación. Solo un spoiler para aquellos dispuestos a probar Branch & Price: 334 es la solución exacta para esta instancia.

Por último, intentemos visualizar los nuevos patrones de corte:

fig, ax = plt.subplots(figsize=[7, 3], dpi=100)hmap = ax.imshow(A > 1e-6, cmap="Blues")plt.axis('off')fig.tight_layout()plt.show()
Patrones de corte producidos en el problema de corte de stock. (Imagen del autor).

Y resolvimos el problema de corte de stock utilizando la generación de columnas.

Lectura adicional

El problema de enrutamiento de vehículos con capacidad (CVRP) fue propuesto por primera vez por Dantzig & Ramser (1959) y es particularmente desafiante debido a su naturaleza combinatoria. Los autores muestran en su artículo original que incluso para problemas pequeños, el número de rutas posibles es increíblemente grande. Por ejemplo, un problema simétrico con 15 puntos de demanda tiene más de 6 × 10⁹ rutas posibles. Me resulta particularmente interesante ver cómo se ha explorado la generación de columnas a lo largo del tiempo en este y otros problemas relacionados.

Aunque para el problema de enrutamiento de vehículos con ventanas de tiempo estrechamente restringidas, la generación de columnas se había establecido desde el trabajo de Desrochers et al. (1992), Branch & Price a menudo fallaba en instancias menos restringidas. Por lo tanto, la generación pura de columnas no se ha considerado como un enfoque prometedor para el CVRP. Sin embargo, Fukasawa et al. (2006) combinaron la generación de columnas en un algoritmo Branch & Cut, demostrando la optimalidad de varias instancias de la literatura. El corte de rama y precio para el CVRP fue mejorado aún más por otros autores y creo que el trabajo de Pecin et al. (2017) puede ser particularmente fascinante para el lector interesado.

Conclusiones

En este artículo, se presentó la generación de columnas retrasada como una estrategia para resolver programas lineales con un gran número de variables de decisión sin considerar todas las variables explícitamente. El problema clásico de corte unidimensional se presentó para ilustrar el método y se implementó una alternativa de solución en Python. El código completo está disponible en este repositorio git.

Referencias

Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W., & Vance, P. H., 1998. Branch-and-price: Column generation for solving huge integer programs. Operations research , 46 (3), 316–329.

de Carvalho, J. V., 1998. Exact solution of cutting stock problems using column generation and branch-and-bound. International Transactions in Operational Research , 5 (1), 35–44.

Dantzig, G. B., & Ramser, J. H., 1959. The truck dispatching problem. Management science , 6 (1), 80–91.

Desrochers, M., Desrosiers, J., & Solomon, M., 1992. A new optimization algorithm for the vehicle routing problem with time windows. Operations research , 40 (2), 342–354.

Fukasawa, R., Longo, H., Lysgaard, J., Aragão, M. P. D., Reis, M., Uchoa, E., & Werneck, R. F., 2006. Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical programming , 106 , 491–511.

Gilmore, P. C., & Gomory, R. E., 1961. A linear programming approach to the cutting-stock problem. Operations research , 9 (6), 849–859.

Irnich, S., & Desaulniers, G., 2005. Shortest path problems with resource constraints (pp. 33–65). Springer US.

Klabjan, D., 2005. Large-scale models in the airline industry. Column generation , 163–195.

Pecin, D., Pessoa, A., Poggi, M., & Uchoa, E., 2017. Improved branch-cut-and-price for capacitated vehicle routing. Mathematical Programming Computation , 9 , 61–100.

Vance, P. H., 1998. Branch-and-price algorithms for the one-dimensional cutting stock problem. Computational optimization and applications , 9 , 211–228.

Winston, W. L. & Goldberg, J. B., 2004. Operations research: applications and algorithms. 4th ed. Belmont, CA: Thomson Brooks/Cole Belmont.

We will continue to update Zepes; if you have any questions or suggestions, please contact us!

Share:

Was this article helpful?

93 out of 132 found this helpful

Discover more

Inteligencia Artificial

Mejora Amazon Lex con características de preguntas frecuentes conversacionales utilizando LLMs

Amazon Lex es un servicio que te permite construir de manera rápida y sencilla bots conversacionales (chatbots), agen...

Inteligencia Artificial

El Enigma para ChatGPT PUMA es un Enfoque de IA que Propone una Forma Rápida y Segura para la Inferencia de LLM

Los Modelos de Lenguaje Grandes (LLMs, por sus siglas en inglés) han comenzado una revolución en el campo de la intel...

Inteligencia Artificial

GitLab presenta Duo Chat una herramienta de IA conversacional para aumentar la productividad

En el desarrollo de software, los desarrolladores enfrentan frecuentemente desafíos al trabajar con código complejo o...

Inteligencia Artificial

7 Lecciones del curso de Aprendizaje Profundo de Fast.AI

Recientemente he terminado el curso de Aprendizaje Profundo Práctico de Fast.AI. He pasado por muchos cursos de ML an...

Ciencia de Datos

Investigadores enseñan a una IA a escribir mejores leyendas de gráficos

Un nuevo conjunto de datos puede ayudar a los científicos a desarrollar sistemas automáticos que generen leyendas más...

Inteligencia Artificial

Conoce a BLIVA un modelo de lenguaje multimodal grande para manejar mejor preguntas visuales ricas en texto

Recientemente, los Modelos de Lenguaje Grande (LLMs) han desempeñado un papel crucial en el campo de la comprensión d...