(N2) Algorithms for Optimization under Uncertainty (Algoritmos de Optimización bajo Condiciones de Incerteza)

cabezal
  • Profesor:  Alberto Marchetti-Spaccamela y Leen Stougie (Sapienza University of Rome, Italia y VU University Amsterdam, Holanda)
  • Horario: Lunes a viernes de 19 a 22 horas
     
  • Aula: A definir (Pabellón 1)
  • Idioma: Inglés
  • Evaluación: Trabajo Práctico de tipo take-home (con entrega el jueves siguiente)


Resumen breve: La optimización combinatoria es una disciplina que combina matemática aplicada y computación teórica. Su objetivo es encontrar la mejor solución entre una cantidad numerable de soluciones posibles. En las técnicas estándar se asume que toda información relevante para el problema es conocida. Sin embargo, esta suposición no siempre es realista: en muchos escenarios se necesita optimizar incluso cuando algunos valores no están completamente determinados; lo cual lleva a que se deban tomar decisiones con datos incompletos. Esta observación ha llevado a la formulación de varios modelos de incertidumbre en optimización. En este curso haremos un repaso de las diversas formas en que la incertidumbre interviene en la optimización.

Programa tentativo:  Día 1: Introducción y motivación. Programación estocástica. Modelos y complejidad. Programación lineal estocástica. Día 2: Resultados de aproximación para problemas de optimización estocástica. Versiones estocásticas para el problema de la mochila y para el del conjunto de cobertura. Día 3: Optimización robusta. Modelos y complejidad. Problemas planificación y ruteo. Día 4: Optimización on-line. Día 5: Modelos híbridos.

 

  • Bibliografía recomendada:
     

• G. Ausiello et al., Complexity and approximation: Combinatorial optimization problems and their approximability properties, 1998, Springer Verlag.
• Martin Dyer, Leen Stougie, Computational complexity of stochastic programming problems, Math. Prog. 2006.
• M. Dyer, R. Kannan and L. Stougie, A simple randomised algorithm for convex optimisation: Application to two-stage stochastic programming, Manuscript.
• David B. Shmoys, Chaitanya Swamy, An Approximation Scheme for Stochastic Linear Programming and its Application to Stochastic Integer Programs. Math. of OR, 2005.
• Leah Epstein, Asaf Levin, Alberto Marchetti-Spaccamela, Nicole Megow, Julian Mestre, Martin Skutella, Leen Stougie, Universal sequencing on a single machine, Manuscript (extended abstract in IPCO 2010).
• Sanjoy Baruah, Vincenzo Bonifaci, Gianlorenzo D'Angelo, Haohan Li, Alberto Marchetti-Spaccamela, Nicole Megow, and Leen Stougie, Scheduling real-time mixed-criticality jobs, Manuscript.

 

  • Notas del curso:

    • Clase 1, Clase 2 y Clase 3 del Prof. Leen Stougie. Son notas que el Prof. hizo para su uso personal en docencia, no son las "notas oficiales" del curso de la ECI, pero sirven como material de apoyo.
    • Apuntes 1, 2 y 3 del Prof. Alberto Marchetti-Spaccamela.
    • Ejercicios de la parte dictada por el Prof. Alberto Marchetti-Spaccamela.
    • Los ejercicios de la parte dictada por el Prof. Leen Stougie se encuentran dentro de los apuntes de las clases.

 

Notas Finales

pie