81675 - CONSTRAINT PROGRAMMING

Scheda insegnamento

  • Docente Zeynep Kiziltan

  • Crediti formativi 6

  • SSD INF/01

  • Modalità di erogazione In presenza (Convenzionale)

  • Lingua di insegnamento Inglese

Anno Accademico 2017/2018

Conoscenze e abilità da conseguire

Questo corso tratta i metodi fondamentali della programmazione a vincoli, in intelligenza artificiale e ricerca operativa, per modellare e risolvere problemi di ottimizzazione a vincoli. I problemi di ottimizzazione a vincoli riguardano i processi di decisione ottimale in presenza di vincoli numerosi e complessi. Tali problemi si presentano spesso in diverse aree scientifiche, aziendali e industriali. Alcuni esempi sono l’allocazione di risorse in un data centre, la configurazione di prodotti in e-commerce e lo scheduling di una linea di montaggio in fabbrica. La difficoltà intrinseca di problemi così cruciali dal punto di vista pratico ha portato allo sviluppo della tecnologia che va sotto il nome di programmazione a vincoli. Molte imprese, tra cui IBM e Oracle, e centri di ricerca nel mondo si avvalgono di questa tecnologia e contribuiscono al suo miglioramento. Ad esempio, la missione Rosetta/Philae lanciata dall’agenzia spaziale europea è stata schedulata e controllata tramite programmazione a vincoli (http://www.a4cp.org/node/1058). Competenze acquisite in questo settore sono quindi spendibili molto bene nel mercato del lavoro. Al termine del corso, lo studente conosce tecniche avanzate di modellazione e metodi risolutivi efficienti, e possiede competenze che gli consentono di modellare problemi usando un linguaggio a vincoli, e di risolverli tramite un risolutore di vincoli. Il corso combina fondamenti teorici con una parte pratica di modellazione e risoluzione di problemi ispirati al mondo reale.

Programma/Contenuti

Introduzione alla programmazione a vincoli.
Tecniche di modellazione.
Nozioni di consistenza locale.
Algoritmi di propagazione di vincoli.
Vincoli globali.
Algoritmi costruttivi di ricerca su alberi
Ottimizzazine.
Scheduling a vincoli.
Metodi di ricerca euristica.
Metodi di ricerca ibrida.
⁠⁠⁠Metodi ibridi di ricerca operativa e programmazione a vincoli.


Testi/Bibliografia

  1. Dispense e bibliografia scientifica forniti dal docente.
  2. Handbook of Constraint Programming. F. Rossi, P. van Beek, T. Walsh (eds), Elsevier Science, 2006.
  3. Hybrid Optimization. M. Milano and P. van Hentenryck (eds), Springer, 2011.

Metodi didattici

Il corso combina fondamenti teorici con una parte pratica di modellazione e risoluzione di problemi ispirati al mondo reale. I metodi didattici consistono in lezioni frontali ed esercizi di programmazione.

Modalità di verifica dell'apprendimento

La verifica dell'apprendimento avviene attraverso un progetto e una prova orale. Il progetto verte sull'applicazione delle tecniche viste a lezione per risolvere un problema (di ottimizzazione) a vincoli, oppure sulla presentazione di un articolo di ricerca. La prova orale consiste in una discussione degli argomenti del corso.

Strumenti a supporto della didattica

Sono utilizzati lucidi che verranno messi sul sito web AMS Campus.

Orario di ricevimento

Consulta il sito web di Zeynep Kiziltan