Algoritmo del Plano de Corte Archivos - Gestión de Operaciones

En un tutorial anterior discutimos sobre la Relajación Lagrangeana, y gracias a dicho ejemplo, vimos que al variar los valores de las variables asociadas a la relajación (más conocidos como los Multiplicadores de Lagrange), el valor de la función objetivo del Problema Dual Lagrangeano se va aproximando al valor que se obtiene al resolver el problema original. En palabras simples, lo que se realizó en ese ejemplo fue optimizar los multiplicadores.

En este artículo, lo que veremos es una forma distinta de optimizar dichas variables, mediante un algoritmo que lleva el nombre de Método de Planos Cortantes o Método de Planos de Corte (o simplemente Planos Cortantes). Este algoritmo también se conoce con el nombre de Cortes basados en Descomposición de Benders, y esto es principalmente debido a que este procedimiento utiliza inecuaciones muy similares a las que se ocupan en el método propuesto por J.F. Benders.

La idea fundamental detrás del algoritmo de planos cortantes es comenzar con una solución inicial factible para el problema relajado, para después “cortar” o sacar dicha solución y cambiarla por otra que mejore el valor de la función objetivo que se está optimizando (es decir el valor del Problema Dual Lagrangeano).

Además, para iniciar este método es necesario tener una consideración especial:

El conjunto de puntos que constituyen las soluciones enteras factibles del problema relajado debe ser acotado.

¿Por qué?: Debido a que el algoritmo de planos cortantes utiliza estos puntos, por lo que si el conjunto fuera no acotado, entonces el algoritmo nunca convergería (es decir, nunca terminaría de iterar). Este conjunto acotado se conoce como la envoltura convexa, pero cuidado: no es cualquiera, es la envoltura convexa de las soluciones enteras del problema relajado.

Veamos entonces cómo funciona este método de forma general. Supongamos que tenemos el siguiente problema, en donde el segundo conjunto de restricciones $Cx\leq d$ es “difícil” y complica la resolución, por lo tanto lo sacamos y lo llevamos a la función objetivo, a lo cual llamaremos el problema relajado:

Además, supongamos que es posible enumerar todos los puntos que son factibles para nuestro problema relajado (es decir, los que están dentro de la envoltura convexa). Si pudiéramos hacer eso, entonces bastaría con evaluar en la función objetivo todos esos puntos, y ver cuál entrega el menor valor: este punto sería entonces nuestra solución óptima.

Lo que se menciona anteriormente, se puede representar matemáticamente de la siguiente forma, donde p es la cantidad de puntos que pertenecen a las soluciones enteras de este problema relajado:

Con lo anterior en consideración, podemos entonces expresar nuestro Problema Dual Lagrangeano de la siguiente forma:

Lo cual, se puede volver a reformular y expresar mediante un problema de optimización. Esta reformulación se conoce como el Problema Maestro, en donde ocupamos una variable auxiliar u y queda expresado de la siguiente forma:

Esta reformulación es importante de entender, ya que gracias a que se dispone de cada uno de los puntos que pertenecen a las soluciones enteras del problema relajado (recuerda que dijimos que se podían enumerar), entonces cada una de las restricciones del tipo:

Constituyen un corte para nuestro problema.

Esto nos lleva a la siguiente pregunta: ¿si tenemos todos los puntos, entonces agregamos todos los cortes inmediatamente (simultáneamente)?

La respuesta es NO, ya que esto sería un trabajo muy tedioso, y tomaría mucho tiempo computacional. Para esto existe el algoritmo de los planos cortantes, para ir agregando iterativamente los cortes, de manera tal que tome menos tiempo que agregarlos todos en conjunto.

Como hemos llamado a la reformulación anterior el Problema Maestro, entonces necesitamos un sub-problema, o problema esclavo. Este sub-problema corresponde al problema relajado que discutimos al principio del desarrollo:

Finalmente, la última pregunta que nos podemos hacer es con cuántos cortes partir. Para la pregunta anterior no hay una respuesta que pudiésemos dar a priori como exacta, pero una buena aproximación es que la cantidad de cortes iniciales (o puntos iniciales a utilizar) sea igual a la cantidad de variables o penalizadores, incrementado en una unidad, es decir:

Número de Cortes Iniciales = Número de Penalizadores + 1

Algoritmo de Planos Cortantes

El algoritmo de planos cortantes se puede enunciar mediante los siguientes pasos. Además, luego encontrarás un resumen mediante un diagrama de flujo:

Sea k=1. Sea x1, x2 ,x3 ,…, xr la cantidad de puntos necesarios para iniciar el algoritmo. Crear los cortes del tipo $\mu \leq c^{T}x_{i}+\lambda ^{T}(Cx_{i}-d)$ con dichos puntos.
Resolver el Problema Maestro.
El problema maestro entregará una actualización para los valores de los Multiplicadores de Lagrange. Con ellos, resolver el sub-problema.
Al resolver el sub-problema, se encontrará un nuevo punto perteneciente a las soluciones factibles del problema relajado. Verificar el criterio de parada. Si se cumple, terminar; sino, crear un nuevo corte.
Agregar el corte al Problema Maestro, hacer k=k+1 y volver a 2.

La teoría de este procedimiento puede ser un poco complicada, así que veamos un ejemplo.

Ejemplo Método de Planos Cortantes

Supongamos el siguiente problema de optimización, en donde las primeras cuatro inecuaciones serán las que permanecen en el problema relajado, y las ultimas 4 son las inecuaciones “complicadas” que serán incorporadas a la función objetivo.

Sin embargo, antes de ello presentaremos una representación gráfica del problema propuesto. El área achurada de color verde corresponde al dominio de soluciones factibles de la relajación continua del problema, es decir, omitiendo las condiciones de integralidad para las variables de decisión.

En este contexto la solución óptima de la relajación continua es el vértice B donde x=30/11 e y=42/11, con valor óptimo V(PL)=186/11=16,909 (aprox).

De forma análoga, la solución óptima del problema entero se encuentra identificado con la letra F con x=3 e y=3, siendo el valor óptimo V(PE)=15.

Notar que la representación gráfica anterior y la obtención de la solución óptima de la relajación continua y del modelo de Programación Entera propuesto tiene un fin sólo ilustrativo, de modo que favorezca la comprensión de los conceptos que presentamos más adelante.

A continuación retomamos el procedimiento del Algoritmo de Planos Cortantes. Para ello escribiremos el problema relajado (no confundir con la relajación continua!) de la siguiente forma:

Al escribir este problema, los puntos pertenecientes a la envoltura convexa de las soluciones enteras del problema relajado son los siguientes:

Una representación gráfica de la envoltura convexa del problema relajado se muestra a continuación:

A pesar de que el método sugiere una cantidad de cortes iniciales, como se puede ver en este ejemplo son sólo 8 puntos (denotados por E, F, G, H, I, J más las coordenadas (2,3) y (3,2)), por lo que no seguiremos esta sugerencia. Para iniciar, hacemos k=1 y utilizaremos el punto (1,4) para crear el siguiente corte:

$\mu \geq 14+8\lambda _{1}-4\lambda _{2}+8\lambda _{3}+23\lambda _{4}$

Por lo que el Problema Maestro en la iteración k=1 es:

Al resolver este problema, la solución óptima es: $\lambda_{1}=0,\lambda_{2}=3,5,\lambda_{3}=0,\lambda_{4}=0,\mu=0$ .

Con estos valores para los Multiplicadores de Lagrange, resolvemos el problema relajado:

El cual, entrega como resultado los valores x=5 e y=1, con un valor objetivo de 58,5.

Luego verificamos el criterio de parada ( $0\neq 58,5$ ) por lo que el nuevo punto que nos permite generar un nuevo corte:

$\mu \geq 13+5\lambda _{1}+13\lambda _{2}+\lambda _{3}+24\lambda _{4}$

Hacemos k=2 y el nuevo Problema Maestro es:

Al resolver este problema, la solución óptima es: $\lambda_{1}=0,\lambda_{2}=0,059,\lambda_{3}=0,\lambda_{4}=0,\mu=13,76$ .

Con estos valores para los Multiplicadores de Lagrange, resolvemos el problema relajado:

El cual, entrega como resultado los valores x=2 e y=4, con un valor objetivo de 15,882.

Verificamos el criterio de parada ( $13,76\neq 15,882$ ) por lo que el nuevo punto que nos permite generar un nuevo corte:

$\mu \geq 16+11\lambda _{1}-2\lambda _{2}+7\lambda _{3}+20\lambda _{4}$

Hacemos k=3 y el nuevo Problema Maestro es:

Al resolver este problema, la solución óptima es: $\lambda_{1}=0,\lambda_{2}=0,2,\lambda_{3}=0,\lambda_{4}=0,\mu=15,6$ .

Con estos valores para los Multiplicadores de Lagrange, resolvemos el problema relajado:

El cual, entrega como resultado los valores x=5 e y=1, con un valor objetivo de 15,6, verificamos el criterio de parada (15,6=15,6), por lo que como se cumple el criterio de parada y el algoritmo se detiene.

Al estar optimizando los valores para una Relajación Lagrangeana, hemos encontrado un valor que cumple con lo siguiente:

$Z_{PE}\leq Z_{H}\leq Z_{PL}$

Particularmente para este problema se cumple que:

$15\leq 15,6\leq 16,909$

Mis sinceros agradecimientos a mi amigo Javier Maturana Ross en la elaboración de este artículo, esperando nos pueda seguir contribuyendo con sus aportes y conocimientos al sitio de Gestión de Operaciones.

Según lo descrito en el artículo Solución del Problema del Vendedor Viajero, una de las situaciones potenciales a la que nos podemos enfrentar es que la solución de asignación obtenida represente un subcircuito, lo cual naturalmente no da respuesta a la problemática que el modelo de agente viajero desea abordar. En este contexto existen diversas estrategias algorítmicas que permiten enfrentar esta situación entre las cuales destaca el Algoritmo de Plano de Corte.

La idea del Algoritmo del Plano de Corte es agregar un conjunto de restricciones que, cuando se incorporan al Problema de Asignación garanticen evitar la formación de un subcircuito. Consideremos un problema con n ciudades, asociar una variable continua $u_{j}\geq 0$ con las ciudades 2,3,…,n. A continuación definir un conjunto de restricciones adicionales de la siguiente forma:

Estas restricciones al añadirse al Modelo de Asignación, eliminarán todas las soluciones de subcircuito de forma automática, pero no eliminarán alguna solución de circuito.

A modo de ejemplo consideremos nuevamente el problema de secuenciamiento de la producción donde nos interesa determinar el orden en el cual se deben producir 4 colores de pintura.

A continuación se define un modelo de optimización haciendo uso del lenguaje de programación matemática AMPL. Para ello se puede utilizar un editor de texto como Bloc de Notas o WordPad. La siguiente imagen muestra la sintaxis utilizada en la definición del modelo del ejemplo propuesto donde se incorpora las restricciones que evitan los subcircuitos. Notar que es importante guardar el archivo con el formato adecuado (.mod) para lo cual simplemente en el caso de utilizar Bloc de Notas seleccionamos «Archivo», seguido de «Guardar como …» y luego en «Nombre» se ingresa un nombre arbitrario seguido de .mod (por ejemplo, modelo.mod).

El siguiente paso es generar un nuevo archivo con los datos o parámetros del problema. Básicamente aquellos que resumen el tiempo (en minutos) necesarios para la limpieza al realizar un cambio de colores, según se describe al inicio de este artículo. Notar que para evitar aquellas asignaciones infactibles (como que a un color le precede el mismo en la secuencia) se asignan «constantes grandes» a los elementos en la diagonal. El archivo se procesa y guarda de forma similar al caso del modelo pero con la extensión .dat (por ejemplo, matriz.dat).

Finalmente será necesario construir un tercer archivo con extensión .run que provee de instrucciones adicionales para efectos de la resolución computacional y que facilita la interpretación de los resultados (por ejemplo, solucion.run).

Una vez definido el modelo, datos y archivo run, podemos utilizar un solver de Programación Entera Mixta de los disponibles en el Servidor NEOS. En particular recomendamos utilizar el solver XpressMP donde se deberá adjuntar los archivos con extensión .mod, .dat y .run (respectivamente) según se muestra a continuación (recordar que el nombre asignado al archivo es arbitrario, no así su extensión).

Luego seleccionamos «Submit to NEOS» y los resultados se mostraran en el navegador de Internet, además de recibir un informe de respuestas en la dirección de correo electrónico que ingresamos. La siguiente imagen muestra un extracto de dichos resultados:

Notar que XpressMP encuentra como recorrido óptimo la secuencia 1-2-4-3-1, es decir, corresponde a producir en el siguiente orden: Blanco, Amarillo, Rojo, Negro, con un tiempo total de setup de 98 minutos.

Etiqueta: Algoritmo del Plano de Corte

Método de Planos Cortantes (Optimización Dual)

Algoritmo de Planos Cortantes

Ejemplo Método de Planos Cortantes

Algoritmo del Plano de Corte en el Problema del Vendedor Viajero