Modelado y Resolución de Problemas de Optimización Discretos

Créditos
4.5
Tipos
Optativa
Requisitos
Esta asignatura no tiene requisitos , pero tiene capacidades previas
Departamento
CS
Los problemas de optimización discreta aparecen en una gran cantidad de dominios que van desde ingeniería, logística, bioinformática, razonamiento probabilístico, asignación de recursos, programación, etc.

En este curso aprenderemos a identificar, modelar y resolver este tipo de problemas. Usaremos el famoso enfoque declarativo en el que el usuario modela el problema con un lenguaje genérico y luego usa una biblioteca genérica de técnicas de resolución.

Para este curso usaremos el lenguaje de modelado MiniZinc y presentaremos tres paradigmas de resolución que se pueden usar con él: satisfacibilidad booleana, programación de restricciones y programación lineal entera. De cada uno cubriremos su poder expresivo y las principales intuiciones detrás de sus técnicas de resolución.

La orientación del curso es esencialmente práctica. Aprenderemos principalmente a través de ejemplos, aunque también se incluirán algunas ideas teóricas.

Profesorado

Responsable

  • Francisco Javier Larrosa Bondia (larrosa@cs.upc.edu)

Horas semanales

Teoría
1
Problemas
1
Laboratorio
1
Aprendizaje dirigido
0
Aprendizaje autónomo
5.65

Objetivos

  1. Capacidad para modelar problemas de optimización discreta y resolverlos con las herramientas más apropiadas
    Competencias relacionadas: CT6, CEA1, CEA13, CG1,

Contenidos

  1. Modelado de problemas combinatorios
    Utilizaremos el lenguaje de modelado MiniZinc para modelar una amplia variedad de problemas. Abarcaremos temas como el modelado de problemas lineales, conjuntos, funciones y el manejo de simetrías, subexpresiones comunes, etc.
  2. Resolucion con programacion con restricciones
    Cubriremos temas como Look-ahead, heurísticas, consistencia local y restricciones globales.
  3. Resolución con técnicas de Lógica Proposicional (SAT)
    Cubriremos temas como la forma normal conjuntiva (CNF), resolución, propagación de clausulas unitarias y aprendizaje de cláusulas.
  4. Resolución con programación lineal entera
    Revisaremos el SIMPLEX y el Branch and Bound

Actividades

Actividad Acto evaluativo


Modelado


Objetivos: 1
Teoría
7h
Problemas
7h
Laboratorio
7h
Aprendizaje dirigido
0h
Aprendizaje autónomo
40h

Programacion con restricciones


Objetivos: 1
Teoría
2h
Problemas
2h
Laboratorio
2h
Aprendizaje dirigido
0h
Aprendizaje autónomo
13h

Satisfactibilitat Booleana



Teoría
3h
Problemas
3h
Laboratorio
3h
Aprendizaje dirigido
0h
Aprendizaje autónomo
13h

Programación Lineal Entera



Teoría
1h
Problemas
1h
Laboratorio
1h
Aprendizaje dirigido
0h
Aprendizaje autónomo
7.5h

Metodología docente

Para la parte de modelado se utilizará el sistema de "flipped classroom" donde los estudiantes tendrán que ver videos y realizar pequeños proyectos. Las horas lectivas se utilizarán para resolver dudas y consolidar conocimientos.

Por la parte de técnicas de resolución se utilizará la metodología clásica de clase magistral y alguna clase de problemas.

Método de evaluación

A lo largo del curso se irán realizando pequeños proyectos con un peso conjunto del 20% de la nota final. También se hará un quizz al inicio del curso, un examen parcial y un examen final con un peso total del 80% de la nota

Bibliografía

Básico

Web links

  • MiniZinc is a high-level constraint modelling language that allows you to easily express and solve discrete optimisation problems. https://www.minizinc.org/

Capacidades previas

Algorítmica básica