Source: https://www.fib.upc.edu/es/estudios/masteres/master-en-innovacion-e-investigacion-en-informatica/plan-de-estudios/asignaturas/CPS-MIRI
Timestamp: 2020-08-11 12:39:57+00:00

Document:
Resolución de Problemas Combinatorios | Facultad de Informática de Barcelona
Inicio » Estudios » Másteres » Máster en Innovación e Investigación en Informática » Plan de estudios » Asignaturas » Resolución de Problemas Combinatorios
http://www.cs.upc.edu/~erodri/cps.html
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.
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,
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,
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,
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.
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.
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.
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.
Introducción a los Problemas Combinatorios
1 . Problemas Combinatorios.
Modelado y resolución con programación con restricciones
2 . Programación con Restricciones.
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.
3 . Programación Lineal.
SAT y Extensiones
Modelado y resolución con SAT y extensiones
4 . Resolución de SAT y extensions.
El examen cubre los temas de modelado y resolución con programación con restricciones, programación lineal y satisfactibilidad proposicional.
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
Trabajo Práctico de Programación Lineal
El proyecto consiste en el modelado y resolución de un problema combinatorio con programación lineal
Trabajo Práctico de SAT
El proyecto consiste en el modelado y resolución de un problema combinatorio con SAT
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
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.
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.
Handbook of satisfiability - Biere, A. [et al.] (eds.), IOS Press, 2009. ISBN: 9781586039295
http://cataleg.upc.edu/record=b1374833~S1*cat
Introduction to algorithms - Cormen, T.H. [et al.], MIT Press, 2009. ISBN: 9780262033848
Handbook of constraint programming - Rossi, F.; Beek, P. van ; Walsh, T. (eds.), Elsevier, 2006. ISBN: 0444527264
http://cataleg.upc.edu/record=b1297310~S1*cat
Model building in mathematical programming - Williams, H.P, Wiley & Sons, 2013. ISBN: 9781118443330
Computational techniques of the simplex method - Maros, I, Kluwer Academic Publishers , 2003. ISBN: 1402073321
http://cataleg.upc.edu/record=b1240297~S1*cat
Website of the couse with slides, materials and diverse information. http://www.cs.upc.edu/~erodri/cps.html
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.

References: Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 

Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución