Resolución de Problemas Combinatorios

Usted está aquí

Inicio » Estudios » Másteres » Máster en Innovación e Investigación en Informática » Plan de estudios » Asignaturas » 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
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

  • Enric Rodriguez Carbonell ( )

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: CB6, CTR6, CEE3.3, CG1, CG3,
  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: CTR6, CEE3.2, CG3,
  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
19.8h

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
10h

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
10h

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
10h

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ásica:

Complementaria:

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.