La generación de columnas o la generación de columnas retrasadas es un algoritmo eficaz para resolver grandes programas lineales .
La idea general es que muchos programas lineales son demasiado grandes para considerar todas las variables de forma explícita. La premisa es que la mayoría de las variables no serán básicas y asumirán un valor de cero en la solución óptima. Debido a esto, en teoría solo es necesario considerar un subconjunto de variables al resolver el problema. La generación de columnas aprovecha esta idea para generar solo las variables que tienen el potencial de mejorar la función objetivo , es decir, para encontrar variables con costo reducido negativo (asumiendo sin pérdida de generalidad que el problema es un problema de minimización).
El problema que se resuelve se divide en dos problemas: el problema principal y el subproblema. El problema principal es el problema original con solo un subconjunto de variables consideradas. El subproblema es un nuevo problema creado para identificar una nueva variable. La función objetivo del subproblema es el costo reducido de la nueva variable con respecto a las variables duales actuales, y las restricciones requieren que la variable obedezca a las restricciones que ocurren naturalmente.
El proceso funciona de la siguiente manera. El problema principal está resuelto; a partir de esta solución, podemos obtener precios duales para cada una de las restricciones del problema principal. Esta información se utiliza luego en la función objetivo del subproblema. El subproblema está resuelto. Si el valor objetivo del subproblema es negativo, se ha identificado una variable con costo reducido negativo. Luego, esta variable se agrega al problema principal y el problema principal se resuelve de nuevo. Resolver el problema principal generará un nuevo conjunto de valores duales, y el proceso se repite hasta que no se identifican variables negativas de costo reducido. El subproblema devuelve una solución con un costo reducido no negativo, podemos concluir que la solución al problema principal es óptima.
En muchos casos, esto permite resolver grandes programas lineales que antes se consideraban 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 , la ruta de los vehículos y el problema de la mediana p capacitada .