Rodrigo Alexander Castro Campos

Trimestres anteriores‎ > ‎2019-O‎ > ‎

1108023 - Temas Selectos de Optimización I

Instructor: Rodrigo Alexander Castro Campos.

Trimestre: 2019-O.

Grupo: CMPOPT01.

Horario: Martes de 11:30 a 14:30, jueves de 13:00 a 14:30.

Salón: E-312 .

Contenido oficial del curso:

Lenguaje de modelado LP.
Introducción a Gurobi.
Generación de modelos mediante programas.
Generación de instancias mediante programas.
Uso avanzado de Gurobi.
Implementación de algoritmos exactos y heurísticos.
Casos de estudio de problemas de optimización.

Calificación:

Habrán al menos seis 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.

17/12: Instalación de Gurobi y lenguaje de modelado LP.
19/12: Lenguaje de modelado LP. Tarea 1 para entrega el 13/01. Calificaciones y una posible solución.
07/01: Modelado de problemas lineales, enteros y cuadráticos.
09/01: El proceso de optimización de modelos. Instancia de mochila y generador del modelo.
14/01: Generación de modelos en LP mediante programas. Instancia de 3matching y generador del modelo.
16/01: Parámetros configurables, soluciones iniciales y la interfaz de programación de Gurobi. Tarea 2 para el 31/01. Calificaciones. Lectura de LP mediante el API.
21/01: Generación de modelos mediante el API de Gurobi. Mochila y 3matching mediante el API.
23/01: Generación de modelos mediante el API de Gurobi. Cuadrados latinos mediante el API. Enlace a problema y generador de modelo.
28/01: Generación de instancias mediante programas. Agente viajero con instancia mediante el API.
30/01: Retrollamadas durante la optimización. Ejemplo de retrollamadas. Tarea 3 para el 24/02. Calificaciones.
04/02: Generación de cortes y restricciones perezosas. Matrices intercaladas mediante el API.
06/02: Contenedores, generadores y algoritmos de la biblioteca de C++.
11/02: Clase cancelada por la asistencia de los alumnos a la VI Escuela de Invierno de Matemáticas Discretas.
13/02: Clase cancelada por la asistencia de los alumnos a la VI Escuela de Invierno de Matemáticas Discretas.
18/02: Generación de números aleatorios. Ejemplo.
20/02: Implementación de simulaciones. Ejemplo. Tarea 4 para el 18/03. Calificaciones.
25/02: Implementación de algoritmos exactos y heurísticos. Ejemplo. Problema, instancia y código de ejemplo.
27/02: El modelo de memoria del hardware y de C++. Ejemplo de paralelización con la biblioteca estándar.
03/03: Paralelismo basado en hilos y basado en tareas. Ejemplo de paralelización con la biblioteca TBB.
05/03: Paralelismo basado en hilos y basado en tareas. Tarea 5 para el 18/03. Calificaciones.
10/03: Implementación de algoritmos metaheurísticos. Tarea 6 para el 18/03. Calificaciones.
12/03: Ejecución cooperativa de Gurobi y algoritmos heurísticos.
Calificaciones finales.

Bibliografía:

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.

Enlaces de interés:

Sitio web de Gurobi: http://www.gurobi.com
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 funciones objetivo: 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
Documentación de Threading Building Blocks (TBB): https://software.intel.com/en-us/tbb-reference-manual
Pruebas de rendimiento entre lenguajes de programación: https://benchmarksgame-team.pages.debian.net/benchmarksgame/
Blog sobre temas de optimización: http://yetanothermathprogrammingconsultant.blogspot.com/
Descripción de MIPGap: http://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/EpGap.html
Reto de optimización discreta Open Research Challenge 2015: https://openresearchchallenge.org/discreteOptimization/ChairofEconomics/The+Challenge

3matching.txt

(1k)

3matching_lp.cpp

(2k)

ayudando_tsp.cpp

(2k)

ayudando_tsp.txt

(202k)

ayudando_tsp_async.cpp

(2k)

ayudando_tsp_tbb.cpp

(2k)

ayudando_tsp_tbb2.cpp

(2k)

calificaciones.txt

(0k)

callback_api.cpp

(1k)

fibonacci.cpp

(0k)

fibonacci_async.cpp

(1k)

horarios.txt

(0k)

horarios_api.cpp

(2k)

intercaladas.cpp

(5k)

latino_api.cpp

(2k)

lectura_lp.cpp

(1k)

matrix.h

(1k)

mochila.txt

(0k)

mochila_api.cpp

(1k)

mochila_lp.cpp

(1k)

random.cpp

(1k)

rectas.txt

(1303k)

simulacion.cpp

(3k)

tarea1.pdf

(30k)

tarea1.txt

(1k)

tarea2.pdf

(59k)

tarea2.txt

(0k)

tarea3.pdf

(48k)

tarea3.txt

(0k)

tarea4.pdf

(68k)

tarea4.txt

(0k)

tarea5.txt

(0k)

tarea6.pdf

(39k)

tarea6.zip

(3k)

tren1.lp

(9969k)

tsp_100.txt

(1k)

tsp_api.cpp

(2k)

tsp_cooperativo.cpp

(5k)