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 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:

1. Sea k=1. Sea x1, x2 ,x3 ,…, xr la cantidad de puntos necesarios para iniciar el algoritmo. Crear los cortes del tipo con dichos puntos.
2. Resolver el Problema Maestro.
3. El problema maestro entregará una actualización para los valores de los Multiplicadores de Lagrange. Con ellos, resolver el sub-problema.
4. 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.
5. 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:

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

Al resolver este problema, la solución óptima es: .

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 () por lo que el nuevo punto que nos permite generar un nuevo corte:

Hacemos k=2 y el nuevo Problema Maestro es:

Al resolver este problema, la solución óptima es: .

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 () por lo que el nuevo punto que nos permite generar un nuevo corte:

Hacemos k=3 y el nuevo Problema Maestro es:

Al resolver este problema, la solución óptima es: .

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:

Particularmente para este problema se cumple que:

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.