Algoritmos en Optimización Combinatoria 
CI-6623


 


        Objetivo: Utilizar el algoritmo primal-dual de programación lineal para derivar los algoritmos eficientes
         conocidos para problemas básicos de optimización combinatoria como son flujo en redes, caminos
         de costo mínimo, apareamientos en grafos. Intersección de matroides: modelo general de muchas
         aplicaciones. Breve introducción a métodos de la programación entera.

         Requisitos: programación lineal, programación, fundamentos de teoría de algoritmos.

        Programa:
        - Introducción: ¿Qué es Optimización Combinatoria?.
        -  Programación Lineal. El algoritmo SIMPLEX
        -  Dualidad
        -  Algoritmo Primal-Dual
        -  Algoritmos primal-dual para flujo máximo y camino mínimo.
        -  Algoritmos primal-dual para flujo de costo mínimo.
        -  Algoritmos eficientes para flujo máximo
        -  Algoritmos para apareamientos máximos y apareamientos con pesos.
        -  Algoritmo de intersección de matroides.
        -  Programación entera: unimodularidad, algoritmos de planos de corte. Separación.

        Bibliografía:
        - Christos H. Papadimitriou y Kenneth Steiglizt. “Combinatorial Optimization: Algorithms and Complexity”.
           Prentice may. 1982. Nueva publicación de Dover Piblications 1998 ISBN 0-486-40258-4.
           cota: QA402.5 P37
        - Alexander Schrijver. “A course in combinatorial optimization”. Notas de curso 1999.
        - Korte y Vygen. “ Combinatorial Optimization: Theory and Algorithms.”. Springer Verlag. 1991
           ISBN- 3-540-67226-5 cota: QA402.5 K6665
        - Wolsey,L. and Nemhauser,G. “Integer and combinatorial optimization”. John Wiley & sons. 1999.
           ISBN 0-471-35943-2. QA402.5 N453

Material:

    - Libro Grafos y Algoritmos (Oscar Meza y Maruja Ortega)

    - Notas de Alexander Schrijver 

Actividades en los trimestres:


Ir al comienzo