Resolución de Problemas Combinatorios

Créditos
6
Tipos
Obligatoria de especialidad (Computación Avanzada)
Requisitos
Esta asignatura no tiene requisitos , pero tiene capacidades previas
Departamento
CS
Web
http://www.cs.upc.edu/~erodri/cps.html
Mail
erodri@cs.upc.edu
Un problema combinatorio consiste en, dada una colección finita de objetos y un conjunto de restricciones, encontrar un objeto de la colección que satisfaga todas las restricciones (y posiblemente que optimice alguna función objetivo). Los problemas combinatorios son omnipresentes y tienen una enorme importancia práctica. En este curso estudiaremos tres paradigmas generales diferentes para resolver problemas combinatorios: programación lineal, satisfactibilidad proposicional y programación con restricciones. Para cada uno de ellos, estudiaremos los fundamentos algorítmicos, así como las técnicas de modelado.

Programa del curso (resumen).
Ejemplos de problemas combinatorios. Paradigmas generales: programación lineal entera, SAT y extensiones, programación con restricciones. Técnicas de modelado y lenguajes.

Profesorado

Responsable

Horas semanales

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

Competencias

Competencias Técnicas de cada especialidad

Advanced computing

  • CEE3.2 - Capacidad para utilizar un espectro amplio y variado de recursos algorítmicos para resolver problemas de alta dificultad algorítmica.
  • CEE3.3 - Capacidad para entender las necesidades computacionales de problemas de disciplinas distintas de la informática y efectuar contribuciones significativas en equipos multidisciplinares que usen la computación.

    • Competencias Técnicas Genéricas

    Genéricas

  • CG1 - Capacidad para aplicar el método científico en el estudio y análisis de fenómenos y sistemas en cualquier ámbito de la Informática, así como en la concepción, diseño e implantación de soluciones informáticas innovadoras y originales.
  • CG3 - Capacidad para el modelado matemático, cálculo y diseño experimental en centros tecnológicos y de ingeniería de empresa, particularmente en tareas de investigación e innovación en todos los ámbitos de la Informática.

    • Competencias Transversales

    Razonamiento

  • CTR6 - Capacidad de razonamiento crítico, lógico y matemático. Capacidad para resolver problemas dentro de su área de estudio. Capacidad de abstracción: capacidad de crear y utilizar modelos que reflejen situaciones reales. Capacidad de diseñar y realizar experimentos sencillos, y analizar e interpretar sus resultados. Capacidad de análisis, síntesis y evaluación.

    • Básicas

  • CB6 - Que los estudiantes sepan aplicar los conocimientos adquiridos y su capacidad de resolución de problemas en entornos nuevos o poco conocidos dentro de contextos más amplios (o multidisciplinares) relacionados con su área de estudio.

    • Objetivos

    1. Modelar problemas surgidos de la informática y otras disciplinas en los paradigmas de resolución considerados en el curso: programación con restricciones, programación lineal entera, satisfactibilidad proposicional.
      Competencias relacionadas: CG1, CG3, CEE3.3, CB6, CTR6,
    2. Familiarizarse con las herramientas del estado del arte de los paradigmas de resolución considerados en el curso: programación con restricciones, programación lineal entera, satisfactibilidad proposicional.
      Competencias relacionadas: CG3, CEE3.2, CTR6,
    3. Comprender los fundamentos algorítmicos de cada uno de los paradigmas de resolución considerados en el curso: programación con restricciones, programación lineal entera, satisfactibilidad proposicional.
      Competencias relacionadas: CEE3.2,

    Contenidos

    1. Problemas Combinatorios.
      Definición informal. Problemas NP-completos vs. problemas de tiempo polinómico. Algunos ejemplos y aplicaciones: satisfactibilidad proposicional, coloración de grafos, mochila, empaquetamiento de contenedores, etc. Enfoques para la resolución de problemas.
    2. Programación con Restricciones.
      Definiciones básicas. Problemas de satisfacción de restricciones. Ejemplos. Consistencia local: consistencia de arco, consistencia de arco direccional, consistencia de límites. Propagación de restricciones para restricciones globales: all different. Algoritmos de búsqueda: retroceso básico, verificación anticipada, búsqueda parcial / completa. Heurísticas de orden de variable y de valor. Problemas de optimización de restricciones. Modelado y resolución de problemas con CP.
    3. Programación Lineal.
      Revisión de programación lineal: el algoritmo del símplex. Dualidad y símplex dual. Modelado y resolución de problemas con programación lineal. Programación lineal entera mixta. Branch & bound, planos de corte, branch & cut. Matrices totalmente unimodulares. Algoritmo del símplex para redes. Modelado y resolución de problemas con programación lineal entera mixta.
    4. Resolución de SAT y extensions.
      Lógica proposicional. El problema de la satisfactibilidad (SAT). Algoritmo DPLL. Resolución. Resolvedores de SAT con aprendizaje de cláusulas guiado por conflictos. Modelado y resolución de problemas con SAT: restricciones de cardinalidad, restricciones pseudo-booleanas. Satisfactibilidad módulo teorías.

    Actividades

    Actividad Acto evaluativo


    Introducción a los Problemas Combinatorios

    Introducción a los Problemas Combinatorios
    Objetivos: 1 2 3
    Contenidos:
    Teoría
    2h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Programación con Restricciones

    Modelado y resolución con programación con restricciones
    Objetivos: 1 2 3
    Contenidos:
    Teoría
    8h
    Problemas
    0h
    Laboratorio
    6h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    12.8h

    Programación Lineal

    Modelado y resolución con programación lineal
    • Teoría: Understanding of the materials given in theory sessions.
    • Laboratorio: Resolution of the practical exercises of each laboratory session.
    • Aprendizaje autónomo: Review and extension of the materials given in theory sessions. Resolution of theoretical exercises.
    Objetivos: 1 2 3
    Contenidos:
    Teoría
    10h
    Problemas
    0h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    20.6h

    SAT y Extensiones

    Modelado y resolución con SAT y extensiones
    • Teoría: Understanding of the materials given in theory sessions.
    • Laboratorio: Resolution of the practical exercises of each laboratory session.
    • Aprendizaje autónomo: Review and extension of the materials given in theory sessions. Resolution of theoretical exercises.
    Objetivos: 1 2 3
    Contenidos:
    Teoría
    8h
    Problemas
    0h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    12.8h

    Examen Final

    El examen cubre los temas de modelado y resolución con programación con restricciones, programación lineal y satisfactibilidad proposicional.
    Objetivos: 1 2 3
    Semana: 16
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Trabajo Práctico de Programación con Restricciones

    El proyecto consiste en el modelado y resolución de un problema combinatorio con programación con restricciones
    Objetivos: 1 2 3
    Semana: 8
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Trabajo Práctico de Programación Lineal

    El proyecto consiste en el modelado y resolución de un problema combinatorio con programación lineal
    Objetivos: 1 2 3
    Semana: 12
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Trabajo Práctico de SAT

    El proyecto consiste en el modelado y resolución de un problema combinatorio con SAT
    Objetivos: 1 2 3
    Semana: 16
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Metodología docente

    La característica principal de la metodología docente es el uso
    de materiales accesibles a través de la web, diseñados específicamente
    para un curso de autoaprendizaje. Estos materiales permiten reformular la
    enseñanza de tal manera que el modelo tradicional de clases desaparece
    en gran medida.

    Así:

    1. Considera la clase como una línea de base para el trabajo, que el
    estudiante debe continuar y profundizar por su cuenta.

    2. Se basa en materiales de alta calidad (diapositivas, listas de
    problemas, problemas resueltos, ejemplos de trabajos prácticos de
    laboratorio, software LP / SAT / CP, referencias bibliográficas).

    3. Tiene como objetivo motivar a los estudiantes, con ejemplos,
    discusiones, comentarios, etc ... Las intuiciones detrás de las
    definiciones, propiedades y las técnicas se discuten en grupo.

    El laboratorio fomentará el trabajo independiente de los estudiantes.
    El papel del profesor será principalmente ayudar y evaluar los
    estudiantes, que deberían trabajar principalmente de forma autónoma.

    Método de evaluación

    El 50% de la nota final corresponde a teoría. Esta nota se obtendrá mediante un examen escrito al final del curso.

    El otro 50% de la nota final corresponde a laboratorio. Esta nota se obtendrá como la media de tres proyectos sucesivos (uno para CP, otro para LP, y todavía otro para SAT) que los estudiantes deberán haber entregado.

    Bibliografía

    Básico

    Complementario

    Web links

    Capacidades previas

    Conocimientos básicos del sistema operativo Linux y del lenguaje de programación C++.
    Conocimientos básicos de álgebra lineal, algoritmos de grafos y lógica.