Saltar al contenido
Volver a los resultados

Generación de Columnas (Dantzig-Wolfe)

Propuesto por
George B. Dantzig and Philip Wolfe
Año
1960
Tipo
algorithm
Familia
Optimization

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

La Generación de Columnas, desarrollada por George B. Dantzig y Philip Wolfe en 1960, es una potente técnica de optimización para resolver problemas de programación lineal a gran escala con estructura especial. También conocida como Descomposición de Dantzig-Wolfe, descompone el problema en un problema maestro (restringido a un subconjunto de variables/columnas) y un subproblema de tarificación (identificación de nuevas variables), mejorando iterativamente la solución mediante la introducción de solo columnas relevantes.

La intuición detrás del método

El método reconoce que muchos problemas de optimización a gran escala tienen una estructura especial: numerosas variables pero pocas restricciones verdaderamente importantes, o subproblemas naturalmente descomponibles. En lugar de resolver el problema completo con todas las variables posibles, la generación de columnas mantiene solo un pequeño subconjunto de columnas (variables) prometedoras. El problema de tarificación, resuelto utilizando costos reducidos y la estructura del problema, identifica nuevas columnas que mejoran la solución maestra. Al agregar iterativamente las columnas más prometedoras, el algoritmo construye una solución de manera eficiente, evitando la carga computacional de manejar todas las columnas simultáneamente.

Historia

Dantzig y Wolfe introdujeron el principio de descomposición para programas lineales en 1960, estableciendo la base teórica. Gilmore y Gomory (1961) lo aplicaron al problema de corte de stock, demostrando su poder práctico. El método ganó prominencia para problemas de ruteo de vehículos y programación en las décadas de 1980-90. La integración con branch-and-bound, creando algoritmos branch-and-price, amplió la aplicabilidad a la programación entera. Las aplicaciones modernas incluyen la programación de tripulaciones de aerolíneas, el ruteo de barcos y la optimización logística a gran escala.

Cuándo usarlo

Aplicar la generación de columnas al resolver programas lineales a gran escala con estructura especial, particularmente cuando el número de variables es enorme pero un pequeño subconjunto domina la solución óptima. Es ideal para problemas de corte de stock, ruteo de vehículos, programación de tripulaciones y empaquetado en contenedores. Úsela cuando la estructura del problema permita una solución eficiente del subproblema de tarificación. Para problemas sin estructura explotable o de tamaño moderado, los solvers de PL estándar son más prácticos.

Limitaciones y consideraciones

  • Requiere una estructura de problema que permita una solución eficiente del subproblema de tarificación
  • La convergencia puede ser lenta, especialmente cerca de la optimalidad (efecto de cola)
  • La solución del subproblema de tarificación debe ser confiable y eficiente, o se pierden las ganancias de eficiencia
  • Complejidad de implementación mayor que los métodos de PL estándar
  • Problemas de estabilidad numérica con grandes valores duales y costos reducidos

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Resuelve problemas a gran escala intratables por métodos estándar debido a la explosión de columnas
  • Explota la estructura del problema para generar solo columnas relevantes
  • Proporciona cotas sobre la calidad de la solución durante la iteración
  • Naturalmente adecuada para problemas con subestructura especial (subproblemas idénticos, simetría)
  • Integrable con branch-and-bound para programas enteros (branch-and-price)

Aplicaciones

  • Problema de corte de stock: minimizar el desperdicio al cortar material en tamaños requeridos
  • Ruteo de vehículos: optimizar rutas para entrega y transporte con ventanas de tiempo y restricciones de capacidad
  • Programación de tripulaciones: asignar miembros de la tripulación a vuelos o turnos minimizando el costo total
  • Empaquetado en contenedores: empacar eficientemente artículos en contenedores para minimizar el desperdicio y el número de contenedores
  • Elaboración de horarios: programar trabajadores en turnos respetando la disponibilidad y las restricciones de preferencia
  • Planificación aérea: programación de vuelos, asignaciones de tripulaciones y coordinación de mantenimiento de aeronaves

Cómo funciona

Cómo funciona

1

Comenzar con un problema maestro restringido que contenga solo un subconjunto de columnas necesarias para una solución factible inicial.

2

Resolver el dual del problema maestro restringido actual utilizando el tableau simplex. Identificar los costos reducidos y configurar el subproblema de tarificación para encontrar variables con costo reducido negativo (para minimización).

3

Resolver el subproblema de tarificación utilizando su estructura especial. Si se encuentra una nueva columna con costo reducido negativo, agregarla al problema maestro y repetir. Si no existe ninguna columna que mejore la solución, la solución actual es óptima.

Errores comunes

  • Seleccionar un algoritmo de subproblema de tarificación ineficiente, negando las ganancias de eficiencia de la generación de columnas
  • No reconocer la estructura del problema susceptible de descomposición, lo que resulta en un rendimiento deficiente
  • Detección de convergencia inadecuada o tolerancia demasiado estricta, desperdiciando iteraciones
  • No implementar técnicas de estabilización para abordar el efecto de cola

Preguntas frecuentes

¿Qué es el problema de tarificación en la generación de columnas y cómo se relaciona con los costos reducidos?

El problema de tarificación identifica nuevas variables (columnas) con costo reducido negativo que mejoran la solución maestra. Los valores de costo reducido provienen del dual del problema maestro restringido y guían la búsqueda en el subproblema de tarificación.

¿Por qué la generación de columnas es mejor que resolver el problema completo con todas las columnas?

En muchos problemas, el número de columnas potenciales es exponencial o infinito, lo que hace imposible enumerarlas todas. La generación de columnas genera solo las columnas necesarias bajo demanda, reduciendo drásticamente la carga computacional.

¿Qué es el efecto de cola y cómo se puede mitigar?

El efecto de cola ocurre cuando la generación de columnas hace un progreso lento cerca de la optimalidad, generando muchas columnas con mejoras mínimas. Las técnicas de estabilización (suavizado dual, métodos de región de confianza, estrategias de corte) reducen su impacto.

¿Cómo extiende branch-and-price la generación de columnas a la programación entera?

Branch-and-price combina la generación de columnas con branch-and-bound: en cada nodo, la generación de columnas resuelve la relajación lineal, y las decisiones de ramificación restringen aún más el problema cuando las soluciones LP son fraccionarias.

Métodos relacionados

Fuentes

  1. Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101-111.

    Abrir referencia DOI
    Copiado.
  2. Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849-859.

    Abrir referencia DOI
    Copiado.