• Descripción

Bienvenidos a la asignatura Optimización Combinatoria, una disciplina de la Investigación Operativa que hace uso también de la Informática, especialmente de algoritmos y de la teoría de la complejidad computacional, para poder desarrollarse.  La optimización combinatoria estudia problemas de los que se consideran "difíciles" (NP-hard), es decir, con un espacio de soluciones muy grande. Los algoritmos de optimización combinatoria tratan de realizar una búsqueda eficiente y eficaz en dicho espacio de búsqueda, obteniendo una buena solución, aunque en general no se pueda garantizar que sea la mejor de todas (óptima). En esta asignatura se introducen conceptos y se diseñan algoritmos para abordar algunos de los problemas de optimización combinatoria más estudiados en la literatura y en la vida real. Dichos algoritmos son conocidos como métodos heurísticos o metaheurísticos. Se estudiarán métodos existentes en la literatura con el objetivo de aprender y proponer nuevos procedimientos para abordar problemas "difíciles", realizando experimentos computacionales y analizando los resultados obtenidos con el objetivo de que los algoritmos propuestos tengan un buen comportamiento, tanto desde el punto de vista de la eficiencia como de la eficacia.

• Información previa a la matrícula

• Profesor Coordinador: Dr. Daniel Riera (http://www.uoc.edu/webs/drierat/ES/curriculum/index.html)
• Créditos: 5
• Descripción: 
• La asignatura trata aquellos problemas en el dominio discreto con un número finito o infinito contable de soluciones. En este tipo de problemas el objetivo es encontrar una (o varias) soluciones de coste lo más cercano posible al óptimo (si no es posible encontrar el óptimo). Algunos ejemplos típicos son los problemas de routing, scheduling, placement, etc. Debida a la explosión combinatoria de posibles soluciones, la búsqueda exhaustiva se hace difícilmente aplicable, especialmente cuando se trata de instancias medianas y grandes del problema. Es por esto que se aplican técnicas incompletas o bien se simplifica el modelo del problema a resolver. La asignatura trata  algunas de las técnicas más utilizadas actualmente: los algoritmos genéticos y evolutivos, la búsqueda tabú, los GRASP, las colonias de hormigas, etc. Estas técnicas se pueden utilizar individualmente o combinarse con el objeto de obtener mejores resultados. 
• Requisitos: Capacidad para leer textos científicos en inglés. Conocimientos básicos de matemáticas (nivel licenciatura o ingeniería).
• Bibliografía prevista: Talbi, E. (2009): Metaheuristics: From Design to Implementation. Wiley.
• Software previsto: compilador Java o C/C++.
• Enlaces: INFORMS (https://www.informs.org/) 
  

• Objetivos y competencias

Los objetivos principales de la asignatura son:

• Introducir a los estudiantes en el área de la optimización combinatoria en general y en algunos de los problemas más estudiados y cotidianos en particular. Conocer los principales tipos de algoritmos heurísticos y metaheurísticos para abordar dichos problemas.

• Diseñar y desarrollar algoritmos para los problemas estudiados, analizando su comportamiento bajo un banco de pruebas formado por instancias de problemas.  

Una vez cursada la asignatura, los estudiantes deben ser capaces de:

• Entender los principales conceptos de la optimización combinatoria.

• Conocer los principales tipos de heurísticos y metaheurísticos para abordar problemas de optimización combinatoria.

• Diseñar y desarrollar algoritmos para algunos de los problemas más estudiados de optimización combinatoria.

• Saber analizar los resultados obtenidos por los métodos desarrollados, realizando comparativas para evaluar su eficiencia y eficacia, utilizando para ello técnicas estadísticas.

• Entender las principales ideas descritas en artículos científicos.

   

• Contenidos

1. Introducción a la optimización combinatoria
2. Principales tipos de algoritmos para abordar problemas de optimización combinatoria
3. Problema de Rutas de Vehículos (VRP)
4. Problema de secuenciación en un taller de flujo (Flowshop)
5. Problema de secuenciación en máquinas paralelas (Parallel machines)
6. Rich VRPs y Simheuristics

• Informaciones sobre la evaluación a la UOC

La Normativa académica de la UOC dispone que el proceso de evaluación se fundamenta en el trabajo personal del estudiante y presupone la autenticidad de la autoría y la originalidad de los ejercicios realizados.

La falta de originalidad en la autoría o el mal uso de las condiciones en las que se hace la evaluación de la asignatura es una infracción que puede tener consecuencias académicas graves.

El estudiante será calificado con un suspenso (D/0) si se detecta falta de originalidad en la autoría de alguna actividad evaluable (práctica, prueba de evaluación continua (PEC) o final (PEF), o la que se defina en el plan docente), ya sea porque ha utilizado material o dispositivos no autorizados, ya sea porque ha copiado de forma textual de internet, o ha copiado de apuntes, de materiales, manuales o artículos (sin la citación correspondiente) o de otro estudiante, o por cualquier otra conducta irregular.

La calificación de suspenso (D/0) en la evaluación continua (EC) puede conllevar la obligación de hacer el examen presencial para superar la asignatura (si hay examen y si superarlo es suficiente para superar la asignatura según indique este plan docente).

Cuando esta mala conducta se produzca durante la realización de las pruebas de evaluación finales presenciales, el estudiante puede ser expulsado del aula, y el examinador hará constar todos los elementos y la información relativos al caso.

Además, esta conducta puede dar lugar a la incoación de un procedimiento disciplinario y la aplicación, si procede, de la sanción que corresponda.

La UOC habilitará los mecanismos que considere oportunos para velar por la calidad de sus titulaciones y garantizar la excelencia y la calidad de su modelo educativo.

• Consulta del modelo de evaluación