Rodrigo Alexander Castro Campos

Trimestres anteriores‎ > ‎2018-O‎ > ‎

1108023 - Temas Selectos de Optimización I

Instructor: Rodrigo Alexander Castro Campos.

Trimestre: 2018-O.

Grupo: CMPOPT01.

Horario: Lunes, miércoles y viernes de 10:00 a 11: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/09: Instalación de Gurobi.
19/09: Lenguaje de modelado LP. Enlaces de interés 1, 2, 3.
21/09: Lenguaje de modelado LP.
24/09: Modelado de problemas lineales enteros y cuadráticos. Tarea 1 para entrega el 01/10. Calificaciones.
26/09: Modelado de problemas lineales enteros y cuadráticos.
28/09: El proceso de optimización de modelos. Instancia de problema.
31/09: Generación de modelos en LP mediante programas. Instancia de problema y código.
01/10: Generación de modelos en LP mediante programas. Tarea 2 para entrega el 12/10. Calificaciones.
03/10: Generación de modelos en LP mediante programas.
05/10: Parámetros configurables y soluciones iniciales.
08:10: Optimización en LP mediante la interfaz de programación de Gurobi y captura de soluciones intermedias.
10/10: Generación de modelos mediante la interfaz de programación de Gurobi. Código de ejemplo.
12/10: Día de descanso obligatorio.
15/10: Generación de modelos mediante la interfaz de programación de Gurobi. Código de ejemplo.
17/10: Generación de números aleatorios con la biblioteca de C y C++.
19/10: Generación de números aleatorios con la biblioteca de C++. Código de ejemplo. Tarea 3 para entrega el 29/10. Calificaciones.
22/10: Generación de instancias mediante programas.
24/10: Contenedores y algoritmos de la biblioteca de C++.
26/10: Implementación de simulaciones.
29/10: Implementación de simulaciones. Código de ejemplo. Tarea 4 para el 19/11 y una sugerencia. Calificaciones.
31/10: Paralelismo basado en hilos y basado en tareas usando la biblioteca estándar de C++.
02/11: Día de descanso obligatorio.
05/11: El modelo de memoria de C++. Código de ejemplo.
07/11: Paralelismo basado en tareas usando la biblioteca TBB. Código de ejemplo.
09/11: No habrá clase por causas de fuerza mayor.
12/11: Implementación de algoritmos exactos. Código de ejemplo 1 y 2.
14/11: Comparación entre implementaciones nativas e interpretadas. Código de ejemplo.
16/11: Implementación de algoritmos heurísticos. Tarea 5 para el 30/11. Calificaciones.
19/11: Implementación de algoritmos metaheurísticos.
21/11: Implementación de algoritmos metaheurísticos. Código de ejemplo.
23/11: Formatos de entrada y salida de datos (texto, JSON, CSV). Código de ejemplo 1, 2, 3, 4.
26/11: Casos de estudio de problemas de optimización. Enlace a presentación en el IMP.
28/11: Modelos mínimos infactibles y captura de múltiples soluciones. Código de ejemplo.
30/11: Uso de múltiples funciones objetivo.
03/12: Generación de cortes y restricciones perezosas. Código de ejemplo.
05/12: Ejemplos de heurísticas guiadas mediante Gurobi. Código de ejemplo.
Calificaciones finales.

Bibliografía:

Gurobi Optimization Inc., Gurobi optimizer reference manual, 2018.
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/8.0/refman/lp_format.html
Documentación de Gurobi, parámetros: http://www.gurobi.com/documentation/8.0/refman/parameters.html
Documentación de Gurobi, atributos: http://www.gurobi.com/documentation/8.0/refman/attributes.html
Documentación de Gurobi, métodos concurrentes: http://www.gurobi.com/documentation/8.0/refman/concurrent_optimizer.html
Documentación de Gurobi, múltiples soluciones: http://www.gurobi.com/documentation/8.0/refman/finding_multiple_solutions.html
Documentación de Gurobi, múltiples funciones objetivo: http://www.gurobi.com/documentation/8.0/refman/multiple_objectives.html
Documentación de Gurobi, referencia de C++: http://www.gurobi.com/documentation/8.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

normal truncada

3matching.cpp

(2k)

3matching.txt

(1k)

3matching_api.cpp

(1k)

IMP.pdf

(398k)

Temario_TSO1.pdf

(65k)

burro.txt

(0k)

calificaciones.txt

(0k)

calificaciones1.txt

(0k)

calificaciones2.txt

(0k)

calificaciones3.txt

(0k)

calificaciones4.txt

(1k)

calificaciones5.txt

(3k)

concurrencia.cpp

(1k)

concurrencia_tbb.cpp

(1k)

conjunto.cpp

(1k)

csv.php

(0k)

ejemplo.csv

(0k)

heuristicas.txt

(0k)

lector_csv1.cpp

(1k)

lector_csv2.cpp

(1k)

mapa_generador.cpp

(1k)

mochila.cpp

(1k)

nota_tarea4.txt

(1k)

permutacion.cpp

(0k)

random.cpp

(0k)

retrollamada.cpp

(0k)

simulacion.cpp

(3k)

tarea1.txt

(1k)

tarea2.txt

(1k)

tarea3.txt

(2k)

tarea4.txt

(2k)

tarea5.txt

(1k)

tsp.cpp

(1k)

tsp_10.txt

(0k)

tsp_100.txt

(1k)

tsp_1000.txt

(6k)

tsp_1000_mst.txt

(10k)

tsp_200.txt

(1k)

tsp_200_mst.txt

(2k)

tsp_22.txt

(0k)

tsp_aleatorio.cpp

(1k)

tsp_generador.cpp

(0k)

tsp_genetico.cpp

(4k)

tsp_gurobi.cpp

(3k)

tsp_gurobi_guiado.cpp

(5k)

tsp_gurobi_lazy.cpp

(3k)

tsp_iterativo.cpp

(2k)

tsp_iterativo.php

(1k)

tsp_multihilo.cpp

(2k)

tsp_recursivo.cpp

(2k)