Resolució de Problemes i Programació amb Restriccions

Esteu aquí

Inici » Estudis » Màsters » Màster en Intel·ligència Artificial » Pla d'estudis » Assignatures » Resolució de Problemes i Programació amb Restriccions
Crèdits
4.5
Tipus
  • MAI: Optativa
  • MEI: Optativa
Requisits
Aquesta assignatura no té requisits, però té capacitats prèvies
Departament
CS
Els problemes d'optimització discreta apareixen en un gran nombre de dominis que van des de l'enginyeria, la logística, la bioinformàtica, el raonament probabilístic, l'assignació de recursos, la programació, etc.

En aquest curs aprendrem a identificar, modelar i resoldre aquest tipus de problemes. Utilitzarem el famós enfocament declaratiu en què l'usuari modela el problema amb un llenguatge genèric i després utilitza una biblioteca genèrica de tècniques de resolució.

Per a aquest curs utilitzarem el llenguatge de modelització MiniZinc i presentarem tres paradigmes de resolució que es poden utilitzar amb ell: Satisfacció booleana, Programació de restriccions i Programació lineal enter. Per a cadascun d'ells tractarem el seu poder expressiu i les principals intuïcions darrere de les seves tècniques de resolució.

L'orientació del curs és essencialment pràctica. Aprendrem principalment a través d'exemples, tot i que també s'hi inclouran algunes idees teòriques.

Professorat

Responsable

  • Francisco Javier Larrosa Bondia ( )

Hores setmanals

Teoria
1
Problemes
1
Laboratori
1
Aprenentatge dirigit
0
Aprenentatge autònom
5.65

Competències

Competències Tècniques Generals

Genèriques

  • CG1 - Capacitat per a projectar, dissenyar i implantar productes, processos, serveis i instal·lacions en tots els àmbits de la Intel·ligència Artificial.

Competències Tècniques de cada especialitat

Acadèmiques

  • CEA1 - Capacitat de comprendre els principis bàsics de funcionament de les tècniques principals dels Sistemes Multiagents, i saber utilitzar-les en l'entorn d'un sistema o servei intel·ligent.
  • CEA13 - Capacitat de comprendre les tècniques avançades de Modelització, Raonament i Resolució de problemes, i saber dissenyar, implementar i aplicar aquestes tècniques en el desenvolupament d'aplicacions, serveis o sistemes intel·ligents.

Competències Transversals

Raonament

  • CT6 - Capacitat d'avaluar i analitzar de manera raonada i crítica sobre situacions, projectes, propostes, informes i estudis de caracter cientific-tecnic. Capacitat d'argumentar les raons que expliquen o justifiquen aquestes situacions, propostes, etc.

Objectius

  1. Capacitat per modelar de manera òptima un problema d'optimització discreta i resoldre'l utilitzant les eines mes adients.
    Competències relacionades: CEA1, CEA13, CG1, CT6,
    Subcompetences:
    • Traduir un problema d'optimització de la vida real en una especificació ben definida amb un lleguatge formal
    • Satisfactibilitat Booleana per resoldre problemes d'optimització discreta
    • Programació amb Restriccions
    • Programació Lineal Entera
    • Cerca Local
    • Traduir un problema d'optimització de la vida real en una especificació ben definida amb un lleguatge formal
    • Satisfactibilitat Booleana per resoldre problemes d'optimització discreta
    • Programació amb Restriccions
    • Programació Lineal Entera
    • Cerca Local

Continguts

  1. Modelat de problemes combinatoris
    Utilitzarem el llenguatge de modelització MiniZinc per modelar una àmplia varietat de problemes. Cobrirem temes com ara la modelització de problemes lineals, conjunts, funcions i com tractar simetries, subexpressions comunes, etc.
  2. Resolució amb Programació amb restriccions
    Tractarem temes com ara el Look-ahead, l'heurística, la consistència local i les restriccions globals.
  3. Resolució amb tècniques de Lògica Proposicional (SAT)
    Tractarem temes com la forma normal conjuntiva (FNC), la resolució, la propagació de clausules unitàries i l'aprenentatge de clàusules.
  4. Resolució amb programació lineal entera
    Revisarem el SIMPLEX i el Branch and Bound

Activitats

Activitat Acte avaluatiu


Modeling


Objectius: 1
Teoria
0h
Problemes
10h
Laboratori
13h
Aprenentatge dirigit
0h
Aprenentatge autònom
50h

Constraint Programming


Objectius: 1
Teoria
4h
Problemes
1h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
5h

Satisfactibilitat Booleana



Teoria
5h
Problemes
1h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
5h

Programació Lineal Entera



Teoria
4h
Problemes
1h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
5h

Metodologia docent

Per la part de modelatge es farà servir el sistema de "flipped classroom" on els estudiants hauràn de veure videos i fer petits projectes. Les hores lectives es faràn servir per resoldre dubtes i consolidar coneixements.

Per la part de tècniques de resolució es farà servir la metodologia clàssica de classe magistral i alguna classe de problemes.

Mètode d'avaluació

Al llarg del curs s'aniran fent petits projectes amb un pes conjunt de 20% de la nota final. També es farà un quizz al començament del curs, un examen parcial i un examen final amb un pes total del 80% de la nota

Bibliografia

Bàsica:

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/

Capacitats prèvies

Algorismia bàsica