La Descomposición de Benders es, como su nombre lo dice, un Método de Descomposición. La idea de este método es bastante simple: dividir para conquistar. El objetivo es literalmente descomponer el problema en dos partes: El Master Problem (Problema Maestro) y el Subproblem (Subproblema) (también llamado Slave Problem o Problema Esclavo). En el siguiente artículo revisaremos de qué se trata el Método de Descomposición de Benders, en conjunto con la presentación de su uso en un pequeño ejemplo.
Esta metodología fue propuesta por J.F. Benders en 1962, su nombre original es Partitioning procedures for solving mixed-variables programming problems, y como su nombre bien lo dice el método está pensado originalmente para problemas de Programación Entera Mixta. Sin embargo, también se puede aplicar en problemas de Programación Lineal.
El Método de Descomposición de Benders trabaja bajo el concepto de las “variables complicadas”, es decir las variables que hacen que nuestro problema se «complique». Si estas variables no existieran (o más bien, conociéramos su valor de forma anticipada) entonces el problema resultante se supone que es considerablemente más fácil de resolver.
En Programación Entera Mixta, se espera que estas variables “complicadas” sean las enteras, las cuales al fijar su valor, dejan un problema resultante que cumple con una característica muy conveniente: es lineal. Y como cumple con esto, entonces podemos hacer uso de todo lo que conocemos sobre Programación Lineal para realizar la optimización de las variables que (en un principio) fijamos.
Veamos entonces brevemente de que se trata el Método de Descomposición de Benders. Supongamos que tenemos un problema que tiene la siguiente estructura:
Como mencionamos al principio, entonces podemos separar este problema en dos partes. A continuación se muestra el Master Problem (Problema Maestro) a la izquierda y el Subproblem (Subproblema) a la derecha:
Como se puede ver, el Master Problem contiene las variables que son enteras, y el Subproblem contiene las variables continuas, por lo que este último cumple con ser un problema de Programación Lineal.
Notar que el lado derecho de las restricciones del problema esclavo son números, ya que los valores de las variables enteras están fijos.
Iniciamos este artículo diciendo que el concepto central es dividir para conquistar: en este caso lo que se hace es resolver el Problema Maestro para obtener los valores de y; con esto, podemos resolver entonces el Subproblema. Se puede observar que el valor de la función objetivo del Subproblema se encuentra en la función objetivo del Problema Maestro, lo anterior se reformulará más adelante.
Una nota relevante: Si te das cuenta, el Problema Maestro para esta formulación no tiene ninguna restricción más que las de dominio. Nada impide que el Problema Maestro también tenga restricciones. Esto estará dado por la estructura del problema que estemos estudiando.
Recuerda siempre: ambos problemas están conectados, por lo que el resultado de uno influye directamente en el resultado del otro. Con esto en consideración, se cumple la siguiente propiedad:
Si el Subproblema es no acotado, entonces el Problema Maestro también lo es, resultando en que el problema original es no acotado.
Si tenemos un problema de Programación Lineal, entonces tenemos que aprovecharlo. ¿Qué es lo primero que se nos viene a la mente con un problema lineal? La respuesta es dualidad. Cada problema lineal (primal) tiene su problema dual asociado, el cual para el caso del problema esclavo enunciado anteriormente, tiene la siguiente estructura:
¿Qué es lo que podemos ver en este problema dual?: Que la región factible (es decir el sub-espacio definido por las restricciones y el dominio del problema) no depende del valor que tomen las variables enteras, y sólo influye en el valor de la función objetivo (notar que están en ella).
Lo anterior entonces nos lleva a la siguiente pregunta: ¿Qué sucede cuando la región factible del problema es vacía? (recuerda que al ser vacía estamos diciendo que nuestro problema dual es infactible). Dos cosas pueden ocurrir:
- Al ser el problema dual infactible, entonces su primal es no acotado para algún valor de las variables enteras, en cuyo caso el problema original también es no acotado, o bien
- La región factible del problema primal es también infactible para todo valor de las variables enteras, llevando a la conclusión de que el problema original es infactible.
¿Por qué revisamos todo esto?: Porque es importante tenerlo en consideración, ya que como mencionamos anteriormente, al tener un problema esclavo lineal, entonces podemos hacer el uso de los conceptos de dualidad.
¿Para qué la usaremos?: Para reformular nuestro Problema Maestro, y transformarlo en lo que usualmente se conoce como Relaxed Master Problem (RMP). Esta reformulación utiliza las variables duales asociadas a las restricciones del Slave Problem primal.
El Relaxed Master Problem (Problema Maestro Relajado) se puede escribir de la siguiente forma:
A las restricciones (1) y (2) se les conoce como restricciones de factibilidad y optimalidad, respectivamente. Además, existe una variable auxiliar z, la cual permite es la responsable de hacer la “conexión” entre el Problema Maestro y el Subproblema (esto se puede ver en las restricciones del tipo (1) y (2)).
Al resolver el RMP vamos a obtener los valores de las variables enteras, las cuales utilizaremos para resolver el Subproblema, como resultado podemos obtener dos cosas:
- El sub-problema es infactible, lo cual implica que el problema dual es no acotado. Si esto ocurre, debemos agregar un corte de factibilidad al RMP.
- El sub-problema tiene una solución óptima, lo cual implica que el problema dual también la tiene. Si esto ocurre, entonces hay que agregar un corte de optimalidad al RMP.
La última pregunta que nos queda por responder es: ¿Cuántas veces iterar?. Para responder lo anterior debemos definir la cota superior e inferior.
La cota superior corresponde al valor de la función objetivo original de nuestro problema; la cota inferior corresponde a la función objetivo del Master Problem, por lo tanto, debemos continuar hasta que ambos valores sean iguales.
Como la teoría de esta descomposición puede ser un poco compleja, veamos un ejemplo.
Ejemplo Método de Descomposición de Benders (Programación Lineal)
El ejemplo que veremos a continuación corresponde a un problema de Programación Lineal. La aplicación es similar para los problemas de Programación Entera Mixta.
Supongamos que tenemos que resolver el siguiente problema:
La solución óptima para este problema es: 
, 
e 
con un valor para la función objetivo (valor óptimo) de 5,285. La solución óptima del problema anterior se puede alcanzar de forma sencilla a través del Método Simplex Dual o el Método Simplex de 2 Fases (y por cierto a través de otros procedimientos y herramientas computacionales como Solver de Excel).
Vamos a descomponer el problema de la siguiente forma: recuerda que utilizaremos el RMP (Problema Maestro Relajado). Sea esta la primera iteración, K=1.
Al resolver el RMP de la primera iteración, obtenemos como solución óptima 
y 
; lo cual utilizaremos para resolver el Subproblema. Con , el resultado del Subproblema es: 
y 
con un valor en la función objetivo de 5,6.
Ahora debemos calcular la cota superior (UB) y cota inferior (LB):
Como difieren el valor de las cotas, debemos continuar. Gracias a la herramienta “Análisis de Sensibilidad” del Solver en Excel, podemos obtener el valor de las variables duales asociadas a las restricciones del Subproblema (también podríamos obtener el valor de las variables duales óptimas al utilizar el Teorema de Holguras Complementarias). Esos valores son: 
y 
.
Estos valores nos permiten crear el siguiente corte de optimalidad: 
, el cual agregamos al Problema Maestro:
Hacemos K=2 (contador de iteraciones) y resolvemos el Problema Maestro nuevamente. Este corte nos permite encontrar una nueva solución óptima: 
y . Con este valor de y, el resultado del Subproblema es: y 
con un valor en la función objetivo de 0,68.
Ahora debemos calcular la cota superior (UB) y cota inferior (LB):
Al ver las variables duales para las restricciones del Subproblema tenemos que: 
y 
, lo cual permite crear el siguiente corte de optimalidad el cual agregamos al Problema Maestro:
Hacemos K=3 y resolvemos el Problema Maestro nuevamente. La nueva solución óptima para el Problema Maestro es y 
con un valor óptimo de 5,285. Con la solución del Subproblema es: y con un valor en la función objetivo de 2,148.
Ahora debemos calcular la cota superior e inferior:
Como ambas cotas (superior e inferior) son iguales, podemos detenernos. Hemos encontrado la solución óptima para nuestro problema de Programación Lineal. (Mis sinceros agradecimientos a mi amigo Javier Maturana Ross por su contribución con este detallado tutorial y los créditos correspondientes al profesor Yuping Huang por el ejemplo presentado en este artículo).
Excelente resumen!!!