Lagrange Archivos - Gestión de Operaciones

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

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.

Ejemplo de Relajación Lagrangeana en Programación Entera

El método de Relajación Lagrangeana (o Relajación Lagrangiana) consiste básicamente en un Método de Descomposición cuya idea se basa en descomponer un problema original restringido, en principio complejo de resolver, de modo de reemplazarlo por otro problema que permita simplificar la resolución. Esto se logra incorporando aquellas restricciones que se consideran difíciles (las que hacen compleja la resolución directa del problema) a la función objetivo, donde cada una de éstas tendrá asociada un Multiplicador de Lagrange $\lambda$ que permitirá (iterativamente) penalizar el incumplimiento de las mismas al ser establecidos distintos valores para los multiplicadores. De esta forma se espera que las restantes restricciones (las que no se incorporan mediante penalizaciones en la función objetivo) permitan verificar un problema cuya resolución sea fácil (o al menos más sencilla que el problema en su estructura original).

El problema asociado a encontrar los valores de $\lambda$ que permitan minimizar la función $LR(\lambda)$ (que en sí es un problema de maximización) se conoce como el Problema Dual Lagrangeano. En general puede resultar un problema tedioso de resolver, no obstante, a continuación se enumeran una serie de pasos que permiten una aproximación a la implementación del método de Relajación Lagrangeana.

Supongamos que el problema original es de Maximización y que la o las restricciones relajadas son inecuaciones del tipo $\leqslant$ :

Comenzar con cada $\lambda$ igual a cero. Definir inicialmente (y de forma arbitraria) un Paso de magnitud k.
Resolver $LR(\lambda)$ de modo de alcanzar la solución óptima en términos de x.
Para cada restricción violada por x, incrementar el correspondiente $\lambda$ por k.
Si han transcurrido m iteraciones desde que se alcanzo la última relajación para el problema dual lagrangeano, disminuir k a la mitad.
Ir al Paso 2.

Para ilustrar el procedimiento anterior consideremos un Problema de la Mochila como el que se describe a continuación:

Luego de resolver el problema de Programación Entera propuesto haciendo uso de Solver de Excel se alcanza la Solución Óptima: $x_{1}=0, x_{2}=0, x_{3}=1, x_{4}=1$ con Valor Óptimo: $V(PE)=13$ .

Relajaremos las Restricciones 1 y 2 incorporando éstas a la función objetivo y dejando exclusivamente las condiciones de binarios para las variables de decisión. Esto da origen a nuestro problema de Relajación Lagrangeana $LR(\lambda)$ :

Consideraremos inicialmente $\lambda_{1}=0$ y $\lambda_{2}=0$ . La resolución de dicha instancia es trivial obteniéndose como Solución Óptima: $x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1$ y Valor Óptimo: $LR(\lambda)=22$ . Notar que la solución alcanzada no satisface la Restricción 1 (sin embargo, se satisface la Restricción 2).

Penalizaremos la Restricción 1 al considerar $\lambda_{1}=0,5$ (penalización arbitrariamente definida como punto de partida) y manteniendo $\lambda_{2}=0$ (dado que la Restricción 2 se satisface). La Solución Óptima es $x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1$ con Valor Óptimo de $LR(\lambda)=20$ . En consecuencia, la penalización establecida resulto ser insuficiente para que se evitara la violación (incumplimiento) de la Restricción 1.

Sea $\lambda_{1}=1$ (aumentamos nuevamente en 0,5 la penalización de la Restricción 1) y $\lambda_{2}=0$ . La Solución Óptima se mantiene: $x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1$ con Valor Óptimo: $LR(\lambda)=18$ .

Sea $\lambda_{1}=1,5$ y $\lambda_{2}=0$ . La Solución Óptima se mantiene: $x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1$ con Valor Óptimo: $LR(\lambda)=16$ . Se sigue violando la Restricción 1.

Sea $\lambda_{1}=2$ y $\lambda_{2}=0$ . La Solución Óptima ahora es: $x_{1}=0, x_{2}=1, x_{3}=0, x_{4}=0$ con Valor Óptimo: $LR(\lambda )=15$ . Ahora se satisfacen las Restricciones 1 y 2, teniendo éstas holguras de 5 y 1, respectivamente. Luego si se decide disminuir la penalización de la Restricción 1 a $\lambda_{1}=1,5$ se vuelve al mismo punto de la iteración anterior. En consecuencia se disminuye la magnitud del paso (penalización) a 0,25 de modo que $\lambda_{1}=1,75$ y $\lambda_{2}=0$ . La Solución Óptima es: $x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=0$ con Valor Óptimo: $LR(\lambda)=15$ .

No obstante, la Restricción 2 no se satisface para esta nueva solución y de esta forma se establecen nuevas penalizaciones: $\lambda_{1}=1,75$ y $\lambda_{2}=0,25$ y que dan origen a la Solución Óptima: $x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1$ con Valor Óptimo: $LR(\lambda)=15$ .

El procedimiento continua de esta forma disminuyendo la magnitud del paso (penalización) cuando resulta necesario. Notar que de esta forma las respectivas penalizaciones pueden aumentar o disminuir al cabo de una iteración. El detalle de las iteraciones realizadas se muestra a continuación:

Para cada iteración k se muestra la penalización aplicada para la Restricción 1 y 2 respectivamente, el criterio para la actualización del Paso, el valor de la función objetivo de la Relajación Lagrangeana $LR(\lambda )$ , la Solución Óptima alcanzada para el problema (destacado con color amarillo), el valor que representa dicha solución óptima al ser evaluada en la función objetivo original V(PE), la holgura de la Restricción 1 (2) (con color rojo se destaca cuando se viola la restricción en una determinada magnitud) y si la solución óptima alcanzada en la iteración k-ésima es factible en el problema original PE).

Según se señala en un tutorial por Michael A. Trick (donde se ha tomado este ejemplo y se ha extendido a un número mayor de iteraciones con ciertas variaciones en la aplicación de las mismas) las penalizaciones “óptimas” (luego de seguir iterando) corresponderán aproximadamente a $\lambda_{1}=1,83$ y $\lambda_{2}=0,33$ , alcanzando $LR(\lambda )=14,67$ que constituye una cota superior del valor óptimo del problema original. La Solución Óptima asociada a este escenario es $x_{1}=0, x_{2}=1, x_{3}=1, x_{4}=0$ que es factible en el problema original y reporta un valor en la función objetivo de 11. Notar que la Solución Óptima del PE) es $x_{1}=0, x_{2}=0, x_{3}=1, x_{4}=1$ con Valor Óptimo de 13.

Método de Lagrange aplicado a un Problema de Programación No Lineal

El método de multiplicadores de Lagrange (el cual es generalizado por las condiciones de optimalidad de Karush-Kuhn-Tucker) permite abordar la resolución de modelos de programación no lineal que consideran restricciones de igualdad. En este sentido y como resulta natural, el dominio de soluciones factibles considerará exclusivamente aquellas soluciones que permiten verificar el cumplimiento de la igualdad de dichas restricciones. Por el contrario, un problema de optimización que considera inecuaciones como restricciones, sólo requiere que éstas se cumplan y no necesariamente se deberá forzar el cumplimiento de ellas en igualdad (activas).

En general las condiciones de Lagrange se aplican a un problema que tiene la siguiente estructura:

Que da origen a la función Lagrangiana asociada a dicho problema:

Consideremos el siguiente problema de Programación No Lineal restringido que nos permitirá ilustrar la aplicación del método de Lagrange.

Notar que el problema adopta la estructura estándar previamente descrita y considera una única restricción de igualdad. No se incluye en particular condiciones de no negatividad, que en caso de estar presentes justificarían la aplicación del Teorema de Karush-Kuhn-Tucker.

En este contexto, un mínimo local para el problema propuesto debe satisfacer las condiciones necesarias de primer orden de Lagrange:

Que da origen al siguiente sistema de ecuaciones:

Donde la resolución es trivial y corresponde a x1=2, x2=2 y λ1=-4. Notar que el multiplicador de Lagrange asociado a una restricción de igualdad es libre de signo, en consecuencia la solución propuesta satisface las condiciones necesarias de primer orden.

Adicionalmente se cumplen las condiciones de segundo orden pues:

Es positiva definida (función objetivo estrictamente convexa y restricción lineal que define un conjunto convexo). Luego, el problema es convexo y en consecuencia x1=2 y x2=2 es mínimo global y solución óptima del problema. Este resultado por cierto es consistente con la representación gráfica del problema, donde la solución óptima corresponde al punto A, donde la restricción (color naranjo) es tangente a la curva de nivel que representa a la circunferencia de menor radio que intercepta el dominio de soluciones factibles.