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

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

Competencias

Competencias Técnicas Genéricas

Genéricas

  • CG1 - Capacidad para proyectar, diseñar e implantar productos, procesos, servicios e instalaciones en todos los ámbitos de la Inteligencia Artificial.

    • Competencias Técnicas de cada especialidad

    Académicas

  • CEA1 - Capacidad de comprender los principios básicos de funcionamiento de las técnicas principales de los Sistemas Multiagentes, y saber utilizarlas en el entorno de un sistema o servicio inteligente.
  • CEA13 - Capacidad de comprender las técnicas avanzadas de Modelización, Razonamiento y Resolución de problemas, y saber diseñar, implementar y aplicar estas técnicas en el desarrollo de aplicaciones, servicios o sistemas inteligentes.

    • Competencias Transversales

    Razonamiento

  • CT6 - Capacidad de evaluar y analizar de manera razonada y critica sobre situaciones, proyectos, propuestas, informes y estudios de caracter cientifico-tecnico. Capacidad de argumentar las razones que explican o justifican tales situaciones, propuestas, etc.

    • 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