Modelatge i Resolució de Problemes d'Optimització Discrets

Crèdits
4.5
Tipus
  • MAI: Optativa
  • MDS: Optativa
  • MEI: Optativa
  • MIRI: 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

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