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

Hores setmanals

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

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àsic

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