La generación de columnas , o generación de columnas perezosas , es un método eficaz para resolver grandes problemas de programación lineal .
La idea general del método es que muchos problemas de programación lineal son demasiado grandes para escribir explícitamente todas las variables. Dado que la mayoría de las variables no se incluirán en la base y, por lo tanto, tendrán un valor de cero en la solución óptima, solo se necesita un subconjunto de las variables para resolver el problema. La generación de columnas respalda esta idea al generar solo aquellas variables que tienen el potencial de mejorar la función objetivo, es decir, solo se buscan variables con un costo reducido negativo (asumimos sin pérdida de generalidad que el problema de minimización es siendo resuelto).
La tarea se divide en dos: la tarea principal y una subtarea. El problema principal es el problema original con la suposición de que solo se considera un subconjunto de variables. Una subtarea es una tarea nueva, cuyo propósito es encontrar nuevas variables. La función objetivo del subproblema es el precio reducido de las variables duales actuales, y las restricciones son generadas por restricciones naturales en las variables.
El proceso funciona de la siguiente manera. Resolvemos el problema principal, de la solución obtenemos variables duales para cada restricción del problema original. Esta información se utiliza en la función objetivo de la subtarea. Resolvemos un subproblema. Si la función objetivo de la subtarea es negativa, se encuentra una variable con un precio reducido negativo y esta variable se agrega al problema principal y se produce la siguiente solución del problema principal. La nueva solución óptima al problema principal dará nuevas variables duales, y el proceso se repite siempre que las soluciones al subproblema den valores negativos. Cuando la solución del subproblema da un valor positivo de la función objetivo, podemos concluir que se ha encontrado la solución óptima al problema principal.
En muchos casos, este enfoque permite resolver grandes problemas de programación lineal. Un ejemplo clásico de la aplicación del método de generación de columnas es el problema de anidamiento . Una técnica de programación lineal que utiliza el mismo enfoque es la descomposición de Danzig-Wolfe . Además, la generación de columnas se usa en muchos problemas, como la programación del trabajo [1] , el enrutamiento y el problema de la mediana p restringida [2] [3] .
Al resolver problemas grandes utilizando el método de base variable (consulte el método simplex , sección "Método de base variable"), a menudo surge un caso similar cuando es posible generar no solo columnas, sino también filas. El método de base variable utiliza el hecho de que en grandes problemas de programación lineal, en los que la mayoría de las restricciones están dadas por desigualdades, la mayoría de las restricciones no alcanzan una restricción estricta (una variable adicional no es igual a cero), lo que significa que tal restricción no puede ser considerado en la solución final. Al resolver problemas con el método de base variable, se puede resolver una subtarea más: determinar la columna de salida. Usando este enfoque, es posible resolver algunos problemas de teoría de juegos (ver, por ejemplo, juegos Blotto ) que contienen millones de filas y columnas.