La descomposición de Dantzig-Wolfe es un algoritmo para resolver problemas de programación lineal con una estructura especial. Fue desarrollado originalmente por George Dantzig y Philip Wolfe y publicado inicialmente en 1960. [1] Muchos textos sobre programación lineal tienen secciones dedicadas a discutir este algoritmo de descomposición . [2] [3] [4] [5] [6] [7]
La descomposición de Dantzig-Wolfe se basa en la generación de columnas retardada para mejorar la manejabilidad de los programas lineales a gran escala. Para la mayoría de los programas lineales resueltos mediante el algoritmo simplex revisado , en cada paso, la mayoría de las columnas (variables) no están en la base. En tal esquema, un problema maestro que contiene al menos las columnas actualmente activas (la base) usa un subproblema o subproblemas para generar columnas para ingresar en la base de manera que su inclusión mejore la función objetivo.
Formulario requerido
Para utilizar la descomposición de Dantzig-Wolfe, la matriz de restricciones del programa lineal debe tener una forma específica. Un conjunto de restricciones debe identificarse como restricciones de "conexión", "acoplamiento" o "complicación" en las que muchas de las variables contenidas en las restricciones tienen coeficientes distintos de cero. Las restricciones restantes deben agruparse en submatrices independientes de modo que si una variable tiene un coeficiente distinto de cero dentro de una submatriz, no tendrá un coeficiente distinto de cero en otra submatriz. Esta descripción se visualiza a continuación:
La matriz D representa las restricciones de acoplamiento y cada F i representa las submatrices independientes. Tenga en cuenta que es posible ejecutar el algoritmo cuando solo hay una submatriz F.
Reformulación del problema
Después de identificar la forma requerida, el problema original se reformula en un programa maestro y n subprogramas. Esta reformulación se basa en el hecho de que cada punto de un poliedro convexo limitado no vacío se puede representar como una combinación convexa de sus puntos extremos .
Cada columna del nuevo programa maestro representa una solución a uno de los subproblemas. El programa maestro impone que se satisfagan las restricciones de acoplamiento dado el conjunto de soluciones de subproblemas que están disponibles actualmente. A continuación, el programa maestro solicita soluciones adicionales del subproblema de modo que se mejore el objetivo general del programa lineal original.
El algoritmo
Si bien existen varias variaciones con respecto a la implementación, el algoritmo de descomposición de Dantzig-Wolfe se puede describir brevemente de la siguiente manera:
- Partiendo de una solución factible al programa maestro reducido, formule nuevas funciones objetivo para cada subproblema de manera que los subproblemas ofrezcan soluciones que mejoren el objetivo actual del programa maestro.
- Los subproblemas se resuelven dadas sus nuevas funciones objetivo. Se ofrece al programa maestro un valor óptimo para cada subproblema.
- El programa maestro incorpora una o todas las columnas nuevas generadas por las soluciones a los subproblemas en función de la capacidad respectiva de esas columnas para mejorar el objetivo del problema original.
- El programa maestro realiza x iteraciones del algoritmo simplex, donde x es el número de columnas incorporadas.
- Si se mejora el objetivo, vaya al paso 1. De lo contrario, continúe.
- El programa maestro no puede mejorarse más con nuevas columnas de los subproblemas, por lo tanto, regrese.
Implementación
Hay ejemplos de la implementación de la descomposición Dantzig – Wolfe disponibles en los lenguajes de modelado matemático AMPL [8] y GAMS [9] . Existe una implementación general paralela disponible [10] que aprovecha el kit de programación lineal GNU de código abierto .
El algoritmo se puede implementar de manera que los subproblemas se resuelvan en paralelo, ya que sus soluciones son completamente independientes. Cuando este es el caso, hay opciones para el programa maestro en cuanto a cómo las columnas deben integrarse en el maestro. El maestro puede esperar hasta que se complete cada subproblema y luego incorporar todas las columnas que mejoran el objetivo o puede elegir un subconjunto más pequeño de esas columnas. Otra opción es que el maestro puede tomar solo la primera columna disponible y luego detener y reiniciar todos los subproblemas con nuevos objetivos basados en la incorporación de la columna más nueva.
Otra opción de diseño para la implementación involucra columnas que salen de la base en cada iteración del algoritmo. Esas columnas se pueden retener, descartar inmediatamente o descartar a través de alguna política después de futuras iteraciones (por ejemplo, eliminar todas las columnas no básicas cada 10 iteraciones).
Una reciente (2001) evaluación computacional de Dantzig-Wolfe en general y Dantzig-Wolfe y computación paralela es la tesis doctoral de JR Tebboth [11]
Ver también
Referencias
- ^ George B. Dantzig; Philip Wolfe (1960). "Principio de descomposición para programas lineales". Investigación operativa . 8 : 101-111. doi : 10.1287 / opre.8.1.101 .
- ^ Dimitris Bertsimas; John N. Tsitsiklis (1997). Optimización lineal . Athena Scientific.
- ^ George B. Dantzig; Mukund N. Thapa (1997). Programación Lineal 2: Teoría y Extensiones . Saltador.
- ^ Vašek Chvátal (1983). Programación lineal . Macmillan.
- ^ Maros, István; Mitra, Gautam (1996). "Algoritmos simplex". En JE Beasley (ed.). Avances en programación lineal y entera . Oxford Science. págs. 1-46. Señor 1438309 .
- ^ Maros, István (2003). Técnicas computacionales del método simplex . Serie Internacional en Investigación de Operaciones y Ciencias de la Gestión. 61 . Boston, MA: Kluwer Academic Publishers. págs. xx + 325. ISBN 1-4020-7332-1. Señor 1960274 .
- ^ Lasdon, Leon S. (2002). Teoría de la optimización para grandes sistemas (reimpresión de la edición de Macmillan de 1970). Mineola, Nueva York: Dover Publications, Inc. págs. Xiii + 523. Señor 1888251 .
- ^ "Repositorio de código AMPL con el ejemplo de Dantzig – Wolfe" . Consultado el 26 de diciembre de 2008 .
- ^ Kalvelagen, Erwin (mayo de 2003), Descomposición de Dantzig-Wolfe con GAMS (PDF) , consultado el 31 de marzo de 2014.
- ^ "Implementación de código abierto Dantzig-Wolfe" . Consultado el 15 de octubre de 2010 .
- ^ Tebboth, James Richard (2001). Un estudio computacional de la descomposición de Dantzig-Wolfe (PDF) (tesis doctoral). Universidad de Buckingham, Reino Unido.