Modelatge i Resolució de Problemes d'Optimització Discrets

Crèdits
4.5
Tipus
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 (larrosa@cs.upc.edu)

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: CT6, CEA1, CEA13, CG1,

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
7h
Problemes
7h
Laboratori
7h
Aprenentatge dirigit
0h
Aprenentatge autònom
40h

Constraint Programming


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

Satisfactibilitat Booleana



Teoria
3h
Problemes
3h
Laboratori
3h
Aprenentatge dirigit
0h
Aprenentatge autònom
13h

Programació Lineal Entera



Teoria
1h
Problemes
1h
Laboratori
1h
Aprenentatge dirigit
0h
Aprenentatge autònom
7.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