1158070 Optimización en redes
Trimestre 2015 Primavera
Instructores: Dra. Laura
Elena Chávez Lomelí, Dr. Marco Antonio Heredia Velasco, Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 4 de mayo a viernes 17 de julio de 2015.
Grupos: CPMOPT01 (lunes,
miércoles y viernes de 10:00 a 11:30).
Asesorías: En la oficinas
H-150, H-287 y H-264.
Salón: E312.
Cupo: 10 alumnos.
Contenido
Se cubrirá el contenido oficial del curso (el cual se detalla
abajo). Los temas serán cubiertos por los diferentes instructores.
- Gráficas, digráficas y redes [MH].
- Problemas de ruta más corta [MH].
- Problemas de flujo máximo [MH].
- Problemas de flujo de costo mínimo [LC].
- Problemas de acoplamientos [LC/FZ].
- Problemas de ruteo [FZ].
Evaluación
Habrá cinco evaluaciones. Cada evaluación valdrá 20 puntos. Se
requiere obtener
- al menos 60 puntos para acreditar con S,
- al menos 73 puntos para acreditar con B y
- al menos 87 puntos para acreditar con MB.
Calendario
El calendario de clases, de entrega de tareas y de evaluaciones que
mostramos abajo es tentativo e irá apareciendo paulatinamente.
- 04/05: Inicio
del curso. Gráficas, digráficas y redes [MH].
- 06/05: Problemas
de ruta más corta [MH]: Costos unitarios.
- 08/05: Problemas
de ruta más corta [MH]: Costos no negativos.
- 11/05: Problemas de ruta más corta [MH]: Costos arbitrarios
sin ciclos negativos.
- 13/05: Problemas de ruta más corta [MH]: Costos arbitrarios.
- 15/05: Día feriado.
- 18/05: Problemas
de flujo máximo [MH]: Modelo y propiedades.
- 20/05: Problemas
de flujo máximo [MH]: Aplicaciones.
- 22/05: Problemas de flujo máximo
[MH]: Algoritmos de camino aumentante.
- 25/05: Problemas de flujo máximo [MH]: Algoritmos de empuje y
re-etiquetado.
- 27/05: Problemas de
flujo máximo [MH]: Algoritmo de contracción aleatoria.
- 29/05: Problemas de flujo máximo [MH]: Flujos multiproducto.
- 01/06: Problemas de flujo
de costo mínimo [LC]: Problemas de flujo de costo mínimo.
- 03/06: Problemas
de flujo de costo mínimo [LC]: Algoritmos primales.
- 05/06: Problemas
de flujo de costo mínimo [LC]: Problema de transbordo.
- 08/06: Problemas de flujo de costo mínimo [LC]: Algoritmo
primal-dual.
- 10/06: Problemas
de flujo de costo mínimo [LC]: Algoritmos de escalamiento dual.
- 12/06: Problemas de flujo de costo
mínimo [LC]: ¿?
- 15/06: Problemas de acoplamientos
[LC]: Acoplamiento máximo en gráficas bipartitas.
- 17/06: Problemas
de acoplamientos [LC]: Acoplamiento bipartito y flujos.
Cubiertas.
- 19/06: Problemas
de acoplamientos [LC]: Acoplamiento máximo en gráficas
generales.
- 22/06: Problemas de acoplamientos [LC]: ¿?
- 24/06: Escuela
de modelación y métodos numéricos.
- 26/06: Escuela
de modelación y métodos numéricos.
- 29/06: Problemas
de acoplamientos [FZ]: ¿?
- 01/07: Problemas
de acoplamientos [FZ]: T-joins.
- 03/07: Problemas
de acoplamientos [FZ]: T-joins.
- 06/07: Problemas de ruteo [FZ]: Problemas de cartero en
gráficas no dirigidas..
- 08/07: Problemas de ruteo [FZ]: Problemas de cartero en
gráficas dirigidas.
- 10/07: Problemas de ruteo [FZ]: Problemas de cartero en
gráficas con viento.
- 13/07: Problemas
de ruteo [FZ]: El algoritmo de Christofides
para circuitos hamiltonianos con costos métricos.
- 15/07: Problemas
de ruteo [FZ]: El algoritmo de Hoogeveen
para caminos hamiltonianos con costos métricos.
- 17/07: Problemas
de ruteo [FZ]: La relajación de Held y Karp
para circuitos hamiltonianos con costos métricos. Análisis de Wolsey.
- 20/07: Fin del curso.
Bibliografía
- Ford Jr. L. R., Fulkerson D. R. (2010). Flows in Networks. Ed.
Princeton University Press.
- Hernández Ayuso M. C. (2005). Introducción a la teoría de
redes. Ed. Sociedad Matemática Mexicana.
- Ahuja R. K., Magnanti T. L., Orlin J. B. (1993). Network
Flows: Theory, Algorithms, and Applications. Ed. Prentice Hall.
- Bertsekas D. P. (1991). Linear Network Optimization:
Algorithms and Codes. Ed. The MIT Press.
- Vazirani V. V. (2010). Approximation Algorithms. Ed. Springer
Berlin Heidelberg.
- Hochbaum D. (Editor). (1996). Approximation Algorithms for
NP-Hard Problems. Ed. Course Technology.
Problemas de flujo
- Bertsekas D.P. (1998). Network Optimization: Continuous and
Discrete Models, Athena Scientific.
- Cook, W. J., Cunningham, W. H., Pulleyblank, W. R. y
Schrijver, A., Combinatorial Optimization, Wiley, New York,
1998.
- Rockafellar, R. T., Network Flows and Monotropic Optimization,
Wiley, New York, 1984.
Problemas de ruta más corta
- Cook W. J, Cunningham W. H., Pulleyblank W. R., Schrijver A.
(1998). Combinatorial Optimization [Chapter 2]. Wiley.
- Cormen T. H., Leiserson C. E., Rivest R. L. (1999).
Introduction to Algorithms [Chapters 23, 25, 26]. McGrawHill.
- Korte B., Vygen J. (2006). Combinatorial Optimization: Theory
and Algorithms [Chapter 7]. Springer.
- Motwani R., Raghavan P. (2006). Randomized Algorithms [Chapter
10]. Cambridge.
- Schrijver A. (2003). Combinatorial Optimization [Chapters 6,
7, 8]. Springer.
Problemas de ruteo
- Cheriyan J., Ravi R. Lecture
Notes on Approximation Algorithms for Network Problems
[Chapters 6, 7].
- Dror M. (2000). Arc Routing: Theory, Solutions, and
Applications. Springer.