Rodrigo Alexander Castro Campos

1158070 - Optimización en Redes

Institución: Universidad Autónoma Metropolitana, Azcapotzalco.
Instructores: Rodrigo Alexander Castro Campos, Marco Antonio Heredia Velasco, Francisco Javier Zaragoza Martínez.
Trimestre: 2024-P.

Grupo: CPMOPT01.
Horario: Lunes, miércoles y viernes de 11:30 a 13:00.
Salón: E312.

Contenido oficial del curso:

Gráficas, digráficas y redes.
Problemas de ruta más corta.
Problemas de flujo máximo.
Problemas de flujo de costo mínimo.
Problemas de acoplamientos.
Problemas de ruteo.

Calificación:

Los temas "problemas de flujo máximo" y "problemas de flujo de costo mínimo" se evaluarán cada uno con una entrega. La entrega consistirá en escribir un programa que construya la gráfica de flujo que modela el problema indicado para la evaluación, y que lo haga correctamente para cualquier entrada válida según la descripción de dicho problema.

De acuerdo al Reglamento de Alumnos de la UAM, es falta de los alumnos en contra de la institución el suplantar o permitir ser suplantado en la realización de actividades académicas y se impondrá desde amonestación escrita hasta suspensión por dos trimestres. Los alumnos que incurran en esta falta no tendrán derecho a aprobar el curso.

Calendario: El calendario es tentativo y podrá cambiar. Pueden consultar programas de ejemplo de los temas del curso.

09/08: Introducción a flujos en gráficas.
12/08: Uso de flujos máximos en la resolución de problemas. Problema "Kill the Werewolf".
14/08: Uso de flujos máximos en la resolución de problemas. Problemas "Division by Two and Permutation" y "Build String" (sin costos).
16/08: Algoritmos de Ford–Fulkerson y Edmonds-Karp.
19/08: Propiedades teóricas del cálculo de flujos máximos. Evaluación del tema "problemas de flujo máximo" para el 04/09. Calificaciones.
21/08: Segunda Feria de Posgrados de la UAM Azcapotzalco.
23/08: Propiedades teóricas del cálculo de flujos máximos. Problema "Coin Grid".
26/08: Algoritmos eficientes para el cálculo de flujos máximos.
28/08: Modelado matemático de problemas de flujos máximos con y sin costo.
30/08: No habrá clase debido a que asistiré a una junta del Comité de Estudios del Posgrado en Optimización.
02/09: Uso de flujos máximos de costo mínimo en la resolución de problemas. Problema "El problema de asignación". Evaluación del tema "problemas de flujo de costo mínimo" para el 18/09. Calificaciones.

Enlaces de interés:

Caso patológico de Ford–Fulkerson: https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/07DemoFordFulkersonPathological.pdf.
Artículo sobre la red de flujo más pequeña para la que Ford-Fulkerson no termina: https://www.jstage.jst.go.jp/article/ipsjjip/24/2/24_390/_article.
Artículo sobre la complejidad de Push-Relabel cuando se seleccionan los vértices más altos con exceso: https://epubs.siam.org/doi/10.1137/0218072.
Demostración de la complejidad de Edmonds-Karp: https://brilliant.org/wiki/edmonds-karp-algorithm
Gurobi en línea para la comunidad UAM: https://callix.azc.uam.mx/rcc/gurobi/.
IDE en línea para la clase en vivo: https://racc.mx/ide/.
Documentación de Gurobi, formato LP: https://www.gurobi.com/documentation/10.0/refman/lp_format.html.
Documentación de Gurobi, interfaz de C++: https://www.gurobi.com/documentation/10.0/refman/cpp_api_overview.html
Lista de problemas de optimización: https://www.csc.kth.se/tcs/compendium/.
Blog sobre temas de optimización: https://yetanothermathprogrammingconsultant.blogspot.com/.