• Inicio

    Materia optativa para la Licenciatura en Ciencias de la Computación y para el Doctorado en Ciencias de la Computación.  Abierta a  alumnos de grado y posgrado de otras carreras.

    Profesora: Irene Loiseau (irene@dc.uba.ar)

    Puntaje para la Lic. en Ciencias de la Computación: 2 puntos 
    Puntaje  para el doctorado en Computación: 3 puntos

    Carga horaria: 3 horas semanales. Clases teóricas y presentaciones de artículos por parte de los alumnos.

    Horario: Miércoles 18 y 30hrs. Aula de seminario del 2do. piso.

    -----------------------------------------------------------

    PROGRAMA:

                  Los problemas de optimización combinatoria ofrecen  interés para su estudio tanto desde el punto de vista teórico como desde el punto de vista de la solución de problemas reales de gran importancia económica y de actualidad.

    El objetivo de esta materia es estudiar problemas de optimización que se modelan como problemas de programación lineal entera. Se presentarán técnicas de resolución de este tipo de modelos que han permitido resolver problemas difíciles de tamaños cada vez mayores. Estudiaremos algunos de estos casos exitosos en detalle.

     Durante el curso habrá clases teóricas y presentaciones de artículos recientes por parte de los alumnos que permitan conocer el estado del arte de la disciplina.

    Temario:

    • Modelado de problemas de programación lineal entera. Ejemplos.
    • Repaso de las nociones básicas de algoritmos branch and bound y de algoritmos branch and cut. Componentes principales de un algoritmo branch and cut 
    • Conjuntos convexos. Definiciones de poliedros. Ejemplos de poliedros. Dimensión. Puntos interiores. Desigualdades válidas, caras y facetas. Descripción completa de un poliedro por facetas. Rayos, puntos extremos y rayos extremos. Descripción de poliedros por medio de puntos y rayos extremos. Teorema de Minkowski..
    • Técnicas de demostración para decidir si una desigualdad es una faceta de un poliedro. Desigualdades válidas generales. Ejemplos de desigualdades válidas para problemas particulares.
    • Reglas de branching para algoritmos branch-and-cut.
    • Preprocesamiento.
    • Algoritmos de generación de columnas (branch and price)
    • Relajación Lagrangeana

    Posteriormente revisaremos en detalle trabajos que describen implementaciones exitosas que sirvieron para resolver distintos problemas (TSP, coloreo, Knapsack, Scheduling, Linear ordering, etc.)

    Bibliografía básica:

    Los siguientes libros pueden servir de base para la mayoría de los temas generales del curso. A medida que avancemos con el curso agregaremos otros trabajos.

    •  Applegate, D., Bixby, R.E., Chvatal, V., Cook,W., The Traveling Salesman Problem, Princeton University Press, 2006.
    •  Chen, D., Batson, R., Dang, Y., Applied Integer Programming, Wiley, 2010.
    • Nemhauser,G.L., Wolsey, L.A., Integer and Combinatorial Optimization, Wiley 1988.
    •  Wolsey, L.A, Integer Programming, Wiley, 1998.