Optimización combinatoria Código:  M0.512    :  5
Consulta de los datos generales   Descripción   Información previa a la matrícula   Objetivos y competencias   Contenidos   Consulta de los materiales de los que dispone la asignatura  
Este es el plan docente de la asignatura para el segundo semestre del curso 2023-2024. Podéis consultar si la asignatura se ofrece este semestre en el espacio del campus Más UOC / La universidad / Planes de estudios). Una vez empiece la docencia, tenéis que consultarlo en el aula. El plan docente puede estar sujeto a cambios.

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.

Amunt

  • 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/

Amunt

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.

     

Amunt

  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

Amunt