La generación de columnas o la generación de columnas retrasadas es un algoritmo eficiente para resolver grandes programas lineales .
La idea general es que muchos programas lineales son demasiado grandes para considerar todas las variables explícitamente. La idea es entonces comenzar resolviendo el programa considerado con solo un subconjunto de sus variables. Luego, iterativamente, se agregan al programa 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 generará una fracción muy pequeña de las variables. Esta esperanza está respaldada por 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 intratables. El ejemplo clásico de un problema en el que se utiliza con éxito es el problema del material de corte . Una técnica particular en 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 la tripulación , las rutas de los vehículos y el problema de la mediana p 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 nuevo problema creado para identificar una variable de mejora ( es decir , que puede mejorar la función objetivo del problema maestro).
La parte más difícil de este procedimiento es cómo 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 de mejora calculando todo el costo reducido y eligiendo una variable con un costo reducido negativo. Por lo tanto, la idea es calcular solo la variable que tiene el costo mínimo reducido. 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 .