Resolución de Problemas y Programación con Restricciones

Créditos
4.5
Tipos
  • MAI: Optativa
  • MEI: 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

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: CEA1, CEA13, CG1, CT6,
    Subcompetences
    • Traducir un problema de optimización real a una especificación bien definida con un lenguaje formal
    • Satisfactibilidad Booleana para resolver problemas de optimización discreta
    • Programación con restricciones
    • Programación Lineal Entera
    • Búsqueda Local
    • Traducir un problema de optimización real a una especificación bien definida con un lenguaje formal
    • Satisfactibilidad Booleana para resolver problemas de optimización discreta
    • Programación con restricciones
    • Programación Lineal Entera
    • Búsqueda Local

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
0h
Problemas
10h
Laboratorio
13h
Aprendizaje dirigido
0h
Aprendizaje autónomo
50h

Programacion con restricciones


Objetivos: 1
Teoría
4h
Problemas
1h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
5h

Satisfactibilitat Booleana



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

Programación Lineal Entera



Teoría
4h
Problemas
1h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
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