|
=========================================================== Column Generation for Integer Programs Jacques
Desrosiers. HEC Montreal and GERAD, Canadá. Transparencias ¡Nuevo! (21/07/03) Resumen: (El curso se dictara en inglés) Los métodos de generación de columnas, que fueron propuestos originalmente para problemas de programación lineal se han mostrado muy eficaces para resolver también problemas de programación entera. En 1958 Ford y Fulkerson sugirieron tratar implícitamente con las variables de un problema de flujo multicommodity. Dantzig y Wolfe en 1960 formalizaron esta idea en su conocido método, en el cual usan una estrategia para incluir las columnas a medida que son necesarias en la solución de un problema de programación lineal. El uso de las técnicas de generación de columnas para problemas de programación lineal entera, en el marco de un esquema Branch and Bound fue introducida por Desrosiers, Soumis y Desrochers en 1984, para resolver un problema de ruteo de vehículos con ventanas de tiempo. A partir de allí podemos encontrar numerosas aplicaciones de este enfoque a distintos problemas de Optimización Combinatoria, como por ejemplo: otros tipos de problemas de ruteo de vehículos, problema de multiples viajeros de comercio, confección de horarios y asignación de tripulaciones en compañías aéreas, programación de vuelos para una aerolínea, inscripción de cursos en una facultad, problemas de particionamiento de grafos en problemas de VLSI y diseño de compiladores, asignación de trafico en sistemas de comunicación de satélites, diseño de redes de comunicaciones, planificación de la producción, optimización de cortes de distintos materiales (cutting stock), problema de conjunto independiente en grafos, problema de máxima satisfabilidad, problema de asignación generalizada, etc. En este curso se presentaran las ideas básicas de estos métodos, un panorama histórico de los mismos, las contribuciones mas recientes y cuales son los aspectos principales que hacen a la buena perfomance de los mismos. =========================================================== |