La descomposición de Benders (o descomposición de Benders ) es una técnica en 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 a menudo ocurre en aplicaciones como la programación estocástica, ya que la incertidumbre generalmente se representa con escenarios. La técnica lleva el 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 un problema maestro de la primera etapa se resuelve sobre el primer conjunto de variables, y los valores para el segundo conjunto de variables se determinan en un segundo conjunto. subproblema de etapa para una solución de primera etapa dada. Si el subproblema determina que las decisiones fijas de la primera etapa son de hecho inviables, entonces se generan los llamados cortes Benders y se agregan al problema maestro, que luego se resuelve 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 denomina " generación de filas ". Por el contrario, la descomposición de Dantzig-Wolfe utiliza " generación de columnas ".
Metodología
Suponga un problema que ocurre en dos o más etapas, donde las decisiones para las etapas posteriores se basan en los resultados de las anteriores. Se puede intentar tomar decisiones en la primera etapa sin un conocimiento previo de la optimización de acuerdo con las decisiones de la etapa posterior. Esta decisión de la primera etapa es el problema principal. Luego, las etapas posteriores pueden analizarse como subproblemas separados. La información de estos subproblemas se devuelve al problema principal. Si se infringieron las restricciones de un subproblema, se pueden volver a agregar al problema principal. A continuación, se resuelve de nuevo el problema principal.
El problema principal representa un conjunto convexo inicial que está aún más limitado por la información recopilada 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 se puede considerar como un límite inferior en la función objetivo del problema general.
La descomposición de Bender es aplicable a problemas con una estructura en gran parte de bloques en diagonal.
Formulación matemática
Suponga un problema de la siguiente estructura:
Dónde representan las restricciones compartidas por ambas etapas de variables y representa el conjunto factible para . Tenga en cuenta que para cualquier, el problema residual es
El dual del problema residual es
Usando la representación dual del problema residual, el problema original se puede reescribir como un problema minimax equivalente
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 a través de un mecanismo de devolución 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 reparado.
Formulación de problemas maestros
Las decisiones para el problema de la primera etapa pueden describirse mediante el problema de minimización más pequeño
Inicialmente, el conjunto de cortes está vacío. Resolver este problema principal constituirá una "primera suposición" en una solución óptima para el problema general, con el valor de ilimitado por debajo y asumiendo cualquier valor factible.
El conjunto de cortes se completará en una secuencia de iteraciones resolviendo el problema interno de maximización de la formulación minimax. Ambos cortes guían el problema maestro hacia un óptimo, si existe, y asegúrese de que es factible para el problema completo. El conjunto de cortes define la relación entre, , e implícitamente .
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 principal en cualquier iteración proporciona un límite inferior en la solución del problema general. Si por algunos el valor objetivo del problema principal es igual al valor del valor óptimo del problema interno, entonces, por la teoría de la dualidad, la solución es óptima.
Formulación de subproblemas
El subproblema considera la solución sugerida al problema principal y resuelve el problema interno de maximización de la formulación minimax. El problema interno se formula utilizando la representación dual
Mientras que el problema principal proporciona un límite inferior al valor del problema, el subproblema se utiliza para obtener un límite superior. El resultado de resolver el subproblema para cualquier puede ser un valor óptimo finito para el que un punto extremo se puede encontrar, una solución ilimitada para la que un rayo extremo en el cono de recesión , o un hallazgo de que el subproblema es inviable.
Procedimiento
En un nivel alto, el procedimiento considerará iterativamente el problema principal y el subproblema. Cada iteración proporciona un límite superior e inferior actualizado en el valor objetivo óptimo. El resultado del subproblema proporciona una nueva restricción para agregar al problema principal 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 el espacio entre el límite superior e inferior es suficientemente pequeño. En tal caso, el valor de se determina resolviendo la solución del problema residual primario .
Formalmente, el procedimiento comienza con el límite inferior establecido en , el límite superior establecido en , y los cortes en el problema maestro están vacíos. Se produce una solución inicial seleccionando cualquier. Luego, el procedimiento iterativo comienza y continúa hasta que el espacio entre el límite superior e inferior es como máximo o se muestra que no existe una solución óptima finita.
El primer paso de cada iteración comienza actualizando el límite superior resolviendo el subproblema dado el valor más reciente de . Hay tres posibles resultados al resolver el subproblema.
En el primer caso, el valor objetivo del subproblema es ilimitado arriba. Según la teoría de la dualidad , cuando un problema dual tiene un objetivo ilimitado, el problema primario correspondiente es inviable. Esto significa que la elección de no satisface para cualquier . Esta solución se puede eliminar del problema principal tomando un rayo extremo que certifica que el subproblema tiene un objetivo ilimitado y agrega una restricción al maestro afirmando que .
En el segundo caso, el subproblema es inviable. Dado que el espacio factible dual del problema está vacío, el problema original no es factible o hay un rayo en el problema primario que certifica que el valor objetivo no está acotado por debajo. En cualquier caso, el procedimiento termina.
En el tercer caso, el subproblema tiene una solución óptima finita. Según la teoría de la 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 actualizar el límite superior 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 principal considere el valor objetivo bajo esta solución particular al afirmar que . Esto aumentará estrictamente el valor de en la solucion en el problema maestro si la elección de fue subóptimo.
Finalmente, la última parte de cada iteración es crear una nueva solución al problema principal resolviendo el problema principal con la nueva restricción. La nueva solucionse 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 la solución del problema residual primario . De lo contrario, el procedimiento continúa con la siguiente iteración.
Ver también
Referencias
- Benders, JF (septiembre de 1962), " Procedimientos de particionamiento 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 de Macmillan de 1970), Mineola, Nueva York: Dover Publications , págs. Xiii + 523, MR 1888251.