Optimización de flujo en redes

Esta es la página de la unidad de aprendizaje Optimización de flujo en redes, impartida en enero-junio 2018 por Arturo Berrones (teoría y fundamentos matemáticos) en colaboración con Elisa Schaeffer (aspectos computacionales) para estudiantes de PISIS de la FIME, UANL.

Hora y lugar

Contenido del curso

  1. Conceptos de ciencia de redes y de optimización de flujo en redes (sistemas que se modelan mediante redes y flujos, grafos Eulerianos y Hamiltonianos, grado, distribución de grado, matriz de adyacencia, problema de ruta más corta, problema de flujo máximo, problema de flujos con costo mínimo) [1, 2, 3].
  2. Introducción a complejidad computacional (Máquinas de Turing y computabilidad. Problemas de decisión. La clase P. Se definen los problemas NP-duros y NP-completos usando la satisfacibilidad Booleana como referencia. A partir de ahí se muestra cómo puede probarse la propiedad NP-completo mediante transitividad). [4].
  3. Algoritmos básicos para los problemas de ruta más corta, flujo máximo y flujos con costo mínimo (Árbol de caminos más cortos. Algoritmo de Dijkstra. Teorema de flujo máximo / corte mínimo. Caminos más cortos sucesivos y conceptos de dualidad para flujos con costo mínimo.) [1, 3].
  4. Aspectos algorítmicos avanzados (Optimalidad y mejoras de costos duales y primales. Métodos de corrección de etiquetas. Algoritmos polinomiales para flujos máximos. Algoritmos polinomiales para flujos con costo mínimo. Otros problemas de flujo en redes.) [1, 3].
  5. Ciencia de redes (aspectos estructurales y jerárquicos, independencia de escala, modelo de Barabási-Albert, redes dinámicas, procesos estocásticos y dinámicos sobre redes) [2 y artículos recientes].

Bibliografía principal

[1] Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: theory, algorithms, and applications.

[2] Barabási, A. L. (2016). Network science. Cambridge university press.

[3] Bertsekas, D. P. (1998). Network optimization: continuous and discrete models (pp. 467- 511). Belmont: Athena Scientific.

[4] Hartmann, A. K., & Weigt, M. (2006). Phase transitions in combinatorial optimization problems: basics, algorithms and statistical mechanics. John Wiley & Sons.

Temario

Calificación

El 50% proviene de dos exámenes (el primero siendo un take-home que se realiza fuera del salón y el segundo siendo tradicional) y cubre las sesiones analíticos de Arturo, mientras la otra mitad proviene de las tareas entregadas a Elisa según el horario. Las seis tareas (cada una siendo continuaciones del trabajo realizado en las tareas y clases anteriores) valen 10 puntos cada una, lo que implica que un alumno puede o realizar todas con éxito parcial o realizar cinco entregas perfectas para completar sus 50 puntos; si un alumno obtiene más de 50 puntos de las tareas, el excedente no se traspasa tal cual a lo que haya faltado de exámenes. Es decir, los puntos de Arturo (máx. 50) se suman con los puntos de Elisa (máx. 50) para obtener la calificación final. La columna PFE corresponde al portafolio de evidencias de las tareas que puede haber recuperado puntos adicionales a través de las correcciones y análisis incluidos en ello. No existen tareas extra de segunda oportunidad, extensiones a las fechas de entrega o revisiones posteriores de tareas ya calificadas. La entrega es siempre al inicio de la sesión de forma presencial según las instrucciones del profesor en cuestión. Repetir en tareas futuras errores ya indicados por los profesores en las revisiones de las tareas anteriores resultará en una reducción de puntos.

Resultados de las tareas computacionales

Enero-junio 2019

Repo T1 T2 T3 T4 T5 T6 PFE Total

Enero-junio 2018

Repo T1 T2 T3 T4 T5 T6 PFE Total
0385 9 10 10 9 10 9 3 50+10
2014 8 9 9 9 9 5 0 49
3079 9 10 9 10 10 8 0 50+6
3921 9 10 9 9 8 NP 5 50
4412 NP NP 4 7 5 5 7+2 30
4644 4 8 5 7 4 3 2 33
5016 8 9 9 9 10 NP 5 50
5040 9 9 8 8 8 NP 3 45
5050 9 9 9 6 8 NP 4 45
5056 9 7 NP 7 6 5 4 38
5064 9 10 6 4 7 8 5 49
6291 9 9 7 9 8 8 5 50+5
7312 9 9 9 10 10 7 3 50+7
MaGa 9 8 8 10 10 8 0 50+3

Herramientas

Para las sesiones con Elisa, es necesario tener instalado una versión reciente de python con la librería NetworkX, una instalación básica de LaTeX para la elaboración de reportes (no se aceptan tareas preparadas en algún otro formato) y una cuenta de GitHub (se requiere uso adecuado de control de versiones y queda prohibido realizar revisiones fuera del repositorio); todo esto es de uso gratuito y obligatorio.

Bibliografía adicional

El mundo está lleno de libros relacionados. Los siguientes libros de texto, que son favoritos personales de Elisa, sirven como material de estudio, aunque asistencia en las clases o estudio de las diapositivas cubrirán los temas esenciales también.

Un material de apoyo de Elisa sobre el diseño y análisis de algoritmos está disponible en PDF.

Actualizada el 7 de diciembre del 2018.
URL: http://elisa.dyndns-web.com/~elisa/teaching/opt/flow/