La generación de columnas o generación de columnas retrasada es un algoritmo eficiente para resolver programas lineales grandes .
La idea general es que muchos programas lineales son demasiado grandes para considerar todas las variables explícitamente. La idea es, por lo tanto, comenzar resolviendo el programa considerado con solo un subconjunto de sus variables. Luego, iterativamente, se agregan al programa las variables que tienen el potencial de mejorar la función objetivo . Una vez que es posible demostrar que agregar nuevas variables ya no mejoraría el valor de la función objetivo, el procedimiento se detiene. La esperanza al aplicar un algoritmo de generación de columnas es que solo se genere una fracción muy pequeña de las variables. Esta esperanza se sustenta en el hecho de que, en la solución óptima, la mayoría de las variables no serán básicas y asumirán un valor de cero, por lo que la solución óptima se puede encontrar sin ellas.
En muchos casos, este método permite resolver grandes programas lineales que de otro modo serían insolubles. El ejemplo clásico de un problema en el que se utiliza con éxito es el problema del corte de material . Una técnica particular en la programación lineal que utiliza este tipo de enfoque es el algoritmo de descomposición de Dantzig-Wolfe . Además, la generación de columnas se ha aplicado a muchos problemas, como la programación de tripulaciones , el enrutamiento de vehículos y el problema de la p-mediana capacitada.
El algoritmo considera dos problemas: el problema maestro y el subproblema. El problema maestro es el problema original en el que solo se considera un subconjunto de variables. El subproblema es un problema nuevo creado para identificar una variable que mejora ( es decir , que puede mejorar la función objetivo del problema maestro).
El algoritmo procede entonces de la siguiente manera:
La parte más difícil de este procedimiento es encontrar una variable que pueda mejorar la función objetivo del problema maestro. Esto se puede hacer encontrando la variable con el costo reducido más negativo (suponiendo, sin pérdida de generalidad , que el problema es un problema de minimización). Si ninguna variable tiene un costo reducido negativo, entonces la solución actual del problema maestro es óptima.
Cuando el número de variables es muy grande, no es posible encontrar una variable que mejore calculando todos los costos reducidos y eligiendo una variable con un costo reducido negativo. Por lo tanto, la idea es calcular solo la variable que tiene el costo reducido mínimo. Esto se puede hacer utilizando un problema de optimización llamado subproblema de fijación de precios que depende en gran medida de la estructura del problema original. La función objetivo del subproblema es el costo reducido de la variable buscada con respecto a las variables duales actuales, y las restricciones requieren que la variable obedezca las restricciones que ocurren naturalmente. El método de generación de columnas es particularmente eficiente cuando esta estructura permite resolver el subproblema con un algoritmo eficiente, típicamente un algoritmo combinatorio dedicado .
A continuación, detallaremos cómo y por qué calcular el coste reducido de las variables. Consideremos el siguiente programa lineal en forma estándar:
al que llamaremos problema primal así como su programa lineal dual :
Además, sean y soluciones óptimas para estos dos problemas que puede proporcionar cualquier solucionador lineal. Estas soluciones verifican las restricciones de su programa lineal y, por dualidad , tienen el mismo valor de la función objetivo ( ) que llamaremos . Este valor óptimo es una función de los diferentes coeficientes del problema primal: . Nótese que existe una variable dual para cada restricción del modelo lineal primal. Es posible demostrar que una variable dual óptima puede interpretarse como la derivada parcial del valor óptimo de la función objetivo con respecto al coeficiente del lado derecho de las restricciones: o de otro modo . Dicho de forma más sencilla, indica cuánto aumenta localmente el valor óptimo de la función objetivo cuando el coeficiente aumenta en una unidad.
Consideremos ahora que una variable no se ha considerado hasta ese momento en el problema primario. Nótese que esto es equivalente a decir que la variable estaba presente en el modelo pero tomó un valor cero. Ahora observaremos el impacto en el problema primario de cambiar el valor de de a . Si y son respectivamente los coeficientes asociados con la variable en la función objetivo y en las restricciones, entonces el programa lineal se modifica de la siguiente manera:
Para saber si es interesante añadir la variable al problema ( es decir , dejar que tome un valor distinto de cero), queremos saber si el valor de la función objetivo de este nuevo problema disminuye a medida que aumenta el valor de la variable . En otras palabras, queremos saber . Para ello, observe que se puede expresar en función del valor de la función objetivo del problema primal inicial: . Podemos entonces calcular la derivada que nos interesa:
En otras palabras, el impacto de cambiar el valor en el valor se traduce en dos términos. Primero, este cambio impacta directamente en la función objetivo y segundo, se modifica el lado derecho de las restricciones, lo que tiene un impacto en las variables óptimas cuya magnitud se mide utilizando las variables duales . La derivada generalmente se denomina costo reducido de la variable y se denotará por en lo sucesivo.
