1158070 Optimización en redes
Trimestre 2014 Primavera
Instructores: Dra. Laura
Elena Chávez Lomelí, Dr. Rafael López Bracho, Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 21 de abril a miércoles 9 de julio de 2014.
Grupos: CPMOPT01 (lunes,
miércoles y viernes de 10:00 a 11:30).
Asesorías: En la oficinas
H-150, H-251 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 [FZ].
- Problemas de ruta más corta [FZ].
- Problemas de flujo máximo [RL].
- Problemas de flujo de costo mínimo [RL].
- Problemas de acoplamientos [LC].
- 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.
- 21/04: Inicio
del curso. Gráficas, digráficas y redes [FZ].
- 23/04: Problemas
de ruta más corta [FZ]: Costos unitarios.
- 25/04: Problemas
de ruta más corta [FZ]: Costos no negativos.
- 28/04: Problemas de ruta más corta [FZ]: Costos arbitrarios
sin ciclos negativos.
- 30/04: Problemas de ruta más corta [FZ]: Costos arbitrarios.
- 02/05: Problemas de ruta más corta [FZ]: .
- 05/05: Día feriado.
- 07/05: Problemas
de flujo máximo [RL]: Modelo y propiedades.
- 09/05: Problemas de flujo máximo
[RL]: Aplicaciones.
- 12/05: Problemas de flujo máximo [RL]: Algoritmos de camino
aumentante.
- 14/05: Problemas de
flujo máximo [RL]: Algoritmos de empuje y re-etiquetado.
- 16/05: Problemas de flujo máximo [RL]: Algoritmo de
contracción aleatoria.
- 19/05: Problemas de flujo
máximo [RL]: Flujos multiproducto.
- 21/05: Problemas
de flujo de costo mínimo [RL]: Problemas de flujo de costo
mínimo.
- 23/05: Problemas
de flujo de costo mínimo [RL]: Algoritmos primales.
- 26/05: Problemas de flujo de costo mínimo [RL]: Problema de
transbordo.
- 28/05: Problemas
de flujo de costo mínimo [RL]: Algoritmo primal-dual.
- 30/05: Problemas de flujo de costo
mínimo [RL]: Algoritmos de escalamiento dual.
- 02/06: Problemas de acoplamientos
[LC]: Acoplamiento máximo en gráficas bipartitas.
- 04/06: Problemas
de acoplamientos [LC]: Acoplamiento bipartito y flujos.
Cubiertas.
- 06/06: Problemas
de acoplamientos [LC]: Acoplamiento máximo en gráficas
generales.
- 09/06: Problemas de acoplamientos [LC].
- 11/06: Problemas de acoplamientos [LC].
- 13/06: No habrá clase.
- 16/06: Problemas
de acoplamientos [LC].
- 18/06: Problemas
de acoplamientos [LC].
- 20/06: Problemas
de acoplamientos [LC].
- 23/06: No hubo clase por causas de
fuerza mayor.
- 25/06: Problemas de ruteo [FZ]: El algoritmo de Christofides
para circuitos hamiltonianos con costos métricos.
- 27/06: Problemas de ruteo [FZ]: El algoritmo de Hoogeveen
para caminos hamiltonianos con costos métricos. Tarea (para el 07/07).
- 30/06: Problemas
de ruteo [FZ]: No hubo clase por causas
de fuerza mayor.
- 02/07: Problemas
de ruteo [FZ]: La relajación de Held y Karp
para circuitos hamiltonianos con costos métricos. Análisis de Wolsey.
- 04/07: Problemas
de ruteo [FZ]: El algoritmo de Frieze,
Galbiati y Maffioli para circuitos hamiltonianos con
costos asimétricos.
- 07/07: Fin del curso.
- 09/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.