Rodrigo Alexander Castro Campos

Rodrigo A. Castro Campos‎ > ‎

1158065 - Laboratorio de Optimización

Instructor: Rodrigo Alexander Castro Campos.

Trimestre: 2021-P.

Grupo: CMPOPT01.

Horario: Lunes, miércoles y viernes de 16:00 a 17:30.

Salón: Página de Facebook (clases en stream), Google Meet.

Contenido oficial del curso:

Algoritmos exactos.
Algoritmos de aproximación. Obtención de cotas.
Heurísticas.
Criterios de comparación de resultados.

Calificación:

Habrán al menos cinco prácticas, las cuales consistirán en la resolución de un problema de optimización que involucre el uso de solucionadores o la implementación de programas. La calificación final se obtiene del promedio de las calificaciones de las prácticas. La escala de calificación en acta es:

Al menos 60 puntos para acreditar con S.
Al menos 73 puntos para acreditar con B.
Al menos 87 puntos para acreditar con MB.

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.

Calendario: El siguiente calendario es tentativo y podrá cambiar a lo largo del curso.

02/08: Presentación del curso. Acceso al servidor de trabajo y comandos básicos.
04/08: Modelado de problemas con programación lineal.
06/08: Lenguaje de modelado LP e introducción a Gurobi. Ejemplos 1, 2, 3.
09/08: Instalación de Gurobi, uso y parámetros de línea de comandos.
11/08: Generación de modelos LP mediante programas. Ejemplo (acoplamiento en gráficas: generador de instancias, generador de LP). Tarea 1 para el 27/08 (archivo de entrada). Calificaciones.
13/08: Sesión de asesoría.
16/08: El proceso de optimización de modelos lineales.
18/08: Cancelada por causas de fuerza mayor.
20/08: La interfaz de programación de Gurobi. Ejemplo de código.
23/08: Generación de modelos mediante el API de Gurobi. Ejemplo de código y ejemplo de entrada.
24/08: Generación de modelos mediante el API de Gurobi. Ejemplo de código y ejemplo de entrada.
25/08: Generación de modelos mediante el API de Gurobi. Ejemplos de código 1a, 1b, 2 y ejemplo de entrada. Tarea 2 para el 13/09. Calificaciones.
27/08: Optimización de modelos multiobjetivo. Ejemplo de código.
30/08: Sesión de asesoría.
01/09: Uso de heurísticas para calcular soluciones iniciales. Ejemplo de código (generador de MST, solucionador).
03/09: Algoritmos de aproximación para calcular soluciones iniciales. Ejemplo de código.
06/09: Retrollamadas y soluciones intermedias. Ejemplos 1 y 2.
08/09: Uso de heurísticas para mejorar soluciones intermedias. Ejemplo de código.
10/09: Retrollamadas y restricciones perezosas. Ejemplo de código. Tarea 3 para el 01/10. Instancia de ejemplo con óptimo de 14. Calificaciones.
13/09: Sesión de asesoría.
15/09: Día de descanso obligatorio.
17/09: Comparación de rendimiento: Gurobi contra otros algoritmos exactos (algoritmos glotones). Ejemplo de código (problema, algoritmo glotón, Gurobi).
20/09: Comparación de rendimiento: Gurobi contra otros algoritmos exactos (programación dinámica). Ejemplo de código.
22/09: Comparación de rendimiento: implementaciones entre lenguajes compilados e interpretados. Ejemplo de código.
24/09: Concurrencia y paralelismo: utilidades básicas de C++. Ejemplo de código (secuencial, thread, async).
27/09: Sincronización entre hilos. Operaciones atómicas. Ejemplo de código (secuencial, paralelo incorrecto, paralelo con operaciones atómicas).
29/09: Líneas de caché y uso compartido falso. Ejemplo de código (secuencial, paralelo incorrecto, paralelo con operaciones atómicas, paralelo con independencia entre hilos, paralelo con uso compartido falso, paralelo sin uso compartido falso).
01/10: Algoritmos concurrentes de la biblioteca de C++. Introducción a la biblioteca TBB. Ejemplo de código (ordenamiento secuencial, ordenamiento paralelo, Fibonacci con política de ejecución, Fibonacci con TBB). Tarea 4 para el 15/10. Instancia de ejemplo. Calificaciones.
04/10: Sesión de asesoría.
06/10: Arreglos concurrentes. Ejemplo de código (arreglos, vectores).
08/10: Paralelismo a nivel instrucción y registros vectoriales. Ejemplo de código.
11/10: Instrucciones vectoriales intrínsecas. Ejemplo de código (número de hilos, AVX2).
13/10: Aplicaciones de paralelismo. Ejemplo de código. Tarea 5 para el 21/10 (instancia de ejemplo, ejecutables lento y rápido). Calificaciones.
15/10: Sesión de asesoría.
Calificaciones finales.

Bibliografía:

Castro Campos. Notas de curso (se irán actualizando conforme avance el trimestre).
Gurobi Optimization Inc., Gurobi optimizer reference manual, 2019.
The C++ Programming Language (4th Edition), Addison-Wesley ISBN 978-0321563842, mayo 2013.
Textos relacionados con la resolución de problemas de optimización mediante solucionadores.

Software necesario o recomendado:

Cliente SSH Bitvise: https://www.bitvise.com/ssh-client-download
Gurobi: http://www.gurobi.com
Intel Threading Building Blocks (TBB): https://software.intel.com/en-us/tbb-reference-manual

Enlaces de interés:

Documentación de C++: http://www.cplusplus.com/reference/
Documentación de Gurobi: http://www.gurobi.com/documentation/
Documentación de Gurobi, formato LP: http://www.gurobi.com/documentation/9.0/refman/lp_format.html
Documentación de Gurobi, tipos de objetivos: https://www.gurobi.com/documentation/9.0/refman/objectives.html
Documentación de Gurobi, tipos de restricciones: https://www.gurobi.com/documentation/9.0/refman/constraints.html
Documentación de Gurobi, parámetros: http://www.gurobi.com/documentation/9.0/refman/parameters.html
Documentación de Gurobi, atributos: http://www.gurobi.com/documentation/9.0/refman/attributes.html
Documentación de Gurobi, métodos concurrentes: http://www.gurobi.com/documentation/9.0/refman/concurrent_optimizer.html
Documentación de Gurobi, múltiples soluciones: http://www.gurobi.com/documentation/9.0/refman/finding_multiple_solutions.html
Documentación de Gurobi, múltiples objetivos: http://www.gurobi.com/documentation/9.0/refman/multiple_objectives.html
Documentación de Gurobi, referencia de C++: http://www.gurobi.com/documentation/9.0/refman/cpp_api_details.html
Pruebas de rendimiento entre lenguajes de programación: https://benchmarksgame-team.pages.debian.net/benchmarksgame/
Funciones intrínsecas de Intel: https://software.intel.com/sites/landingpage/IntrinsicsGuide
Blog sobre temas de optimización: http://yetanothermathprogrammingconsultant.blogspot.com/

3matching.cpp

(2k)

acoplamiento_lp.cpp

(1k)

ejemplo1.lp

(0k)

ejemplo2.lp

(0k)

ejemplo3.lp

(0k)

ejemplo_api.cpp

(1k)

generador_puntos.cpp

(0k)

mochila4.txt

(0k)

mochila_api.cpp

(2k)

notas.pdf

(386k)

puntos9.txt

(0k)

puntos20.txt

(0k)

puntos25.txt

(0k)

puntos30.txt

(0k)

puntos90.txt

(1k)

puntos900.txt

(15k)

tarea1.pdf

(73k)

tarea1.txt

(0k)

tarea1_entrada.txt

(12k)

tarea2.pdf

(57k)

tsp1a.cpp

(3k)

tsp1b.cpp

(3k)

tsp2.cpp

(2k)

tsp_aleatorio.cpp

(2k)

tsp_mst.cpp

(3k)

tsp_objn.cpp

(3k)

tsp_callback_coop.cpp