Descomposición de Bender

Técnica en programación matemática

La descomposición de Benders (o descomposición de Benders ) es una técnica de programación matemática que permite la solución de problemas de programación lineal muy grandes que tienen una estructura de bloques especial . Esta estructura de bloques se da a menudo en aplicaciones como la programación estocástica , ya que la incertidumbre suele representarse con escenarios. La técnica recibe su nombre de Jacques F. Benders .

La estrategia detrás de la descomposición de Benders se puede resumir como divide y vencerás . Es decir, en la descomposición de Benders, las variables del problema original se dividen en dos subconjuntos de modo que se resuelva un problema maestro de primera etapa sobre el primer conjunto de variables, y los valores para el segundo conjunto de variables se determinan en un subproblema de segunda etapa para una solución dada de primera etapa. Si el subproblema determina que las decisiones fijas de la primera etapa son de hecho inviables, entonces se generan los llamados cortes de Benders y se agregan al problema maestro, que luego se vuelve a resolver hasta que no se puedan generar cortes. Dado que la descomposición de Benders agrega nuevas restricciones a medida que avanza hacia una solución, el enfoque se llama " generación de filas ". En contraste, la descomposición de Dantzig-Wolfe utiliza " generación de columnas ".

Metodología

Supongamos que un problema se desarrolla en dos o más etapas, en las que las decisiones para las etapas posteriores dependen de los resultados de las anteriores. Se puede intentar tomar decisiones en la primera etapa sin tener conocimiento previo de la optimalidad de acuerdo con las decisiones de las etapas posteriores. Esta decisión de la primera etapa es el problema principal. Las etapas posteriores se pueden analizar como subproblemas separados. La información de estos subproblemas se devuelve al problema principal. Si se violaron las restricciones de un subproblema, se pueden volver a agregar al problema principal. Luego, el problema principal se resuelve nuevamente.

El problema maestro representa un conjunto convexo inicial que se ve restringido por la información obtenida de los subproblemas. Debido a que el espacio factible solo se reduce a medida que se agrega información, el valor objetivo de la función maestra proporciona un límite inferior para la función objetivo del problema general.

La descomposición de Benders se aplica a problemas con una estructura predominantemente diagonal en bloques.

Formulación matemática

Supongamos un problema con la siguiente estructura:

${\displaystyle {\begin{aligned}&{\text{minimize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} +\mathbf {d} ^{\mathrm {T} }\mathbf {y} \\&{\text{subject to}}&&A\mathbf {x} +B\mathbf {y} \geq \mathbf {b} \\&&&\mathbf {y} \in Y\\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}}$

Donde representan las restricciones compartidas por ambas etapas de variables y representa el conjunto factible para . Nótese que para cualquier , el problema residual es fijo ${\displaystyle A,B}$ ${\displaystyle Y}$ ${\displaystyle \mathbf {y} }$ ${\displaystyle \mathbf {\bar {y}} \in Y}$

${\displaystyle {\begin{aligned}&{\text{minimize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} +\mathbf {d} ^{\mathrm {T} }\mathbf {\bar {y}} \\&{\text{subject to}}&&A\mathbf {x} \geq \mathbf {b} -B\mathbf {\bar {y}} \\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}}$

El dual del problema residual es

${\displaystyle {\begin{aligned}&{\text{maximize}}&&(\mathbf {b} -B\mathbf {\bar {y}} )^{\mathrm {T} }\mathbf {u} +\mathbf {d} ^{\mathrm {T} }\mathbf {\bar {y}} \\&{\text{subject to}}&&A^{\mathrm {T} }\mathbf {u} \leq \mathbf {c} \\&&&\mathbf {u} \geq \mathbf {0} \end{aligned}}}$

Utilizando la representación dual del problema residual, el problema original puede reescribirse como un problema minimax equivalente.

${\displaystyle \min _{\mathbf {y} \in Y}\left[\mathbf {d} ^{\mathrm {T} }\mathbf {y} +\max _{\mathbf {u} \geq \mathbf {0} }\left\{(\mathbf {b} -B\mathbf {y} )^{\mathrm {T} }\mathbf {u} \mid A^{\mathrm {T} }\mathbf {u} \leq \mathbf {c} \right\}\right].}$

La descomposición de Benders se basa en un procedimiento iterativo que elige valores sucesivos de sin considerar el problema interno, excepto a través de un conjunto de restricciones de corte que se crean mediante un mecanismo de retorno a partir del problema de maximización. Aunque la formulación minimax está escrita en términos de , para un óptimo, el correspondiente se puede encontrar resolviendo el problema original con fijo. ${\displaystyle \mathbf {y} }$ ${\displaystyle (\mathbf {u} ,\mathbf {y} )}$ ${\displaystyle \mathbf {\bar {y}} }$ ${\displaystyle \mathbf {\bar {x}} }$ ${\displaystyle \mathbf {\bar {y}} }$

Formulación de problemas maestros

Las decisiones para el problema de la primera etapa se pueden describir mediante el problema de minimización más pequeño.

${\displaystyle {\begin{aligned}&{\text{minimize}}&&\mathbf {z} \\&{\text{subject to}}&&\{{\text{cuts}}\}\\&&&\mathbf {y} \in Y\\\end{aligned}}}$

Inicialmente, el conjunto de cortes está vacío. Resolver este problema maestro constituirá una "primera estimación" de una solución óptima para el problema general, con el valor de ilimitado por debajo y tomando cualquier valor factible. ${\displaystyle \mathbf {z} }$ ${\displaystyle \mathbf {y} }$

El conjunto de cortes se completará en una secuencia de iteraciones mediante la solución del problema de maximización interna de la formulación minimax. Los cortes guían el problema maestro hacia un óptimo , si existe, y garantizan que sea factible para el problema completo. El conjunto de cortes define la relación entre , y implícitamente . ${\displaystyle \mathbf {y} }$ ${\displaystyle \mathbf {y} }$ ${\displaystyle \mathbf {y} }$ ${\displaystyle \mathbf {z} }$ ${\displaystyle \mathbf {x} }$

Dado que el valor de comienza sin restricciones y solo agregamos restricciones en cada iteración, lo que significa que el espacio factible solo puede reducirse, el valor del problema maestro en cualquier iteración proporciona un límite inferior para la solución del problema general. Si para algunos el valor objetivo del problema maestro es igual al valor del valor óptimo del problema interno, entonces, según la teoría de la dualidad, la solución es óptima. ${\displaystyle z}$ ${\displaystyle \mathbf {\bar {y}} }$

Formulación de subproblemas

El subproblema considera la solución propuesta para el problema maestro y resuelve el problema de maximización interna a partir de la formulación minimax. El problema interno se formula utilizando la representación dual ${\displaystyle \mathbf {\bar {y}} }$

${\displaystyle {\begin{aligned}&{\text{maximize}}&&(\mathbf {b} -B\mathbf {\bar {y}} )^{\mathrm {T} }\mathbf {u} +\mathbf {d} ^{\mathrm {T} }\mathbf {\bar {y}} \\&{\text{subject to}}&&A^{\mathrm {T} }\mathbf {u} \leq \mathbf {c} \\&&&\mathbf {u} \geq \mathbf {0} \end{aligned}}}$

Mientras que el problema maestro proporciona un límite inferior para el valor del problema, el subproblema se utiliza para obtener un límite superior. El resultado de resolver el subproblema para cualquier valor dado puede ser un valor óptimo finito para el cual se puede encontrar un punto extremo, una solución ilimitada para la cual se puede encontrar un rayo extremo en el cono de recesión o un hallazgo de que el subproblema es inviable. ${\displaystyle \mathbf {\bar {y}} }$ ${\displaystyle \mathbf {\bar {u}} }$ ${\displaystyle \mathbf {\bar {u}} }$

Procedimiento

En un nivel alto, el procedimiento considerará iterativamente el problema maestro y el subproblema. Cada iteración proporciona un límite superior e inferior actualizados para el valor objetivo óptimo. El resultado del subproblema proporciona una nueva restricción para agregar al problema maestro o un certificado de que no existe una solución óptima finita para el problema. El procedimiento termina cuando se demuestra que no existe una solución óptima finita o cuando la brecha entre el límite superior y el inferior es suficientemente pequeña. En tal caso, el valor de se determina resolviendo el problema residual primario fijando . ${\displaystyle \mathbf {\bar {x}} }$ ${\displaystyle \mathbf {\bar {y}} }$

Formalmente, el procedimiento comienza con el límite inferior establecido en , el límite superior establecido en y los cortes en el problema maestro vacíos. Se produce una solución inicial seleccionando cualquier . Luego comienza el procedimiento iterativo y continúa hasta que la brecha entre el límite superior y el inferior sea como máximo o se demuestre que no existe una solución óptima finita. ${\displaystyle -\inf }$ ${\displaystyle \inf }$ ${\displaystyle \mathbf {\bar {y}} \in Y}$ ${\displaystyle \epsilon }$

El primer paso de cada iteración comienza actualizando el límite superior mediante la solución del subproblema dado el valor más reciente de . Hay tres resultados posibles para la solución del subproblema. ${\displaystyle \mathbf {\bar {y}} }$

En el primer caso, el valor objetivo del subproblema no tiene límites superiores. Según la teoría de la dualidad , cuando un problema dual tiene un objetivo no acotado, el problema primario correspondiente es inviable. Esto significa que la elección de no satisface para ningún . Esta solución se puede eliminar del problema maestro tomando un rayo extremo que certifique que el subproblema tiene un objetivo no acotado y agregando una restricción al problema maestro que afirme que . ${\displaystyle \mathbf {\bar {y}} }$ ${\displaystyle A\mathbf {x} +B\mathbf {\bar {y}} \geq \mathbf {b} }$ ${\displaystyle \mathbf {x} \geq \mathbf {0} }$ ${\displaystyle \mathbf {\bar {u}} }$ ${\displaystyle (\mathbf {b} -B\mathbf {y} )^{\mathrm {T} }\mathbf {\bar {u}} \leq \mathbf {0} }$

En el segundo caso, el subproblema es inviable. Como el espacio factible dual del problema está vacío, o bien el problema original no es factible o bien existe un rayo en el problema primario que certifica que el valor objetivo no está acotado por debajo. En cualquiera de los casos, el procedimiento termina.

En el tercer caso, el subproblema tiene una solución óptima finita. Por la teoría de dualidad para programas lineales, el valor óptimo del subproblema es igual al valor óptimo del problema original restringido a la elección de . Esto permite que el límite superior se actualice al valor de la solución óptima del subproblema, si es mejor que el límite superior actual. Dado un punto extremo óptimo , también produce una nueva restricción que requiere que el problema maestro considere el valor objetivo bajo esta solución particular al afirmar que . Esto aumentará estrictamente el valor de en la solución en el problema maestro si la elección de fue subóptima. ${\displaystyle \mathbf {\bar {y}} }$ ${\displaystyle \mathbf {\bar {u}} }$ ${\displaystyle z\geq (\mathbf {b} -B\mathbf {y} )^{\mathrm {T} }\mathbf {\bar {u}} +\mathbf {d} ^{\mathrm {T} }\mathbf {y} }$ ${\displaystyle z}$ ${\displaystyle \mathbf {\bar {y}} }$ ${\displaystyle \mathbf {\bar {y}} }$

Finalmente, la última parte de cada iteración es crear una nueva solución al problema maestro resolviendo el problema maestro con la nueva restricción. La nueva solución se utiliza para actualizar el límite inferior. Si la brecha entre el mejor límite superior e inferior es menor que entonces el procedimiento termina y el valor de se determina resolviendo el problema residual primario que fija . De lo contrario, el procedimiento continúa con la siguiente iteración. ${\displaystyle (\mathbf {\bar {y}} ,z)}$ ${\displaystyle \epsilon }$ ${\displaystyle \mathbf {\bar {x}} }$ ${\displaystyle \mathbf {\bar {y}} }$

Véase también

• El solucionador FortSP utiliza la descomposición de Benders para resolver problemas de programación estocástica

Referencias

• Benders, JF (septiembre de 1962), "Procedimientos de partición para resolver problemas de programación de variables mixtas", Numerische Mathematik 4(3): 238–252.
• Lasdon, Leon S. (2002), Optimization Theory for Large Systems (reimpresión de la edición Macmillan de 1970), Mineola, Nueva York: Dover Publications , pp. xiii+523, MR  1888251.