69441 - OPTIMIZATION MODELS AND ALGORITHMS M

Scheda insegnamento

Anno Accademico 2019/2020

Conoscenze e abilità da conseguire

The goal of the course is to deal with Integer Programming that is a very powerful tool for modeling combinatorial optimization problems arising in many branches of engineering, industry and resource allocation. The first part of the course covers the modeling aspects of the field, providing the tools for constructing effective mathematical models, i.e., models that can be solved in practice. The second part is devoted to the algorithmic aspects: basic algorithms are reviewed and more sophisticated ones, useful for those models characterized by a large number of variables and/or constraints, are presented in detail. Finally, the third part of the course discusses real-world applications. At the end of the course students are able to formalize a combinatorial problem taken for the real life and run specific tools and algorithms for solving it in practice.

Programma/Contenuti

Prerequisiti: si richiede una buona conoscenza dei concetti di base della teoria degli insiemi e del calcolo vettoriale e matriciale.

Il corso viene fornito in inglese: le slide e gli esercizi sono in inglese. L'esame deve essere sostenuto in inglese.

Il corso riguarda problemi di ottimizzazione in ambito decisionale con particolare attenzione ai problemi di Ottimizzazione Combinatoria. Il primo obiettivo del corso e' di insegnare la teoria che riguarda la Programmazione Lineare e la Programmazione Lineare Intera, e come formulare modelli matematici per problemi di ottimizzazione appartenenti a tali categorie. Vengono presentati i problemi classici di Programmazione Lineare Intera e vengono presentate alcune formulazioni. Il secondo obiettivo e' di presentare algoritmi esatti ed euristici per la risoluzione di tali problemi. Inoltre, vengono introdotto i concetti di base della complessita' computazionale e i problemi classici modellati su grafo. L'ultima parte del corso e' dedicata alle applicazioni pratiche: vengono presentate applicazioni reali di ottimizzazione e si mostra l'utilizzo di software di ottimizzazione.

Testi/Bibliografia

Slide disponibili su IOL (Insegnamenti On Line)

Per approfondimenti:
Christos H. Papadimitriou and Ken Steiglitz, Combinatorial optimization: algorithms and complexity. Dover, 1998.

D. Bertsimas and J. Tsitsiklis, Introduction to linear programming. Dynamic Ideas and Athena Scientific, Belmont, Massachusetts, 2008.

D. Bertsimas, D. and R. Weismantel, Optimization over integers. Dynamic Ideas, Belmont, Massachusetts, 2005.

Metodi didattici

Il corso consiste in lezioni frontali ed esercitazioni.

Modalità di verifica dell'apprendimento

L'esame consiste in un compito scritto in cui lo studente risolve alcuni esercizi e risponde ad alcune domande sui contenuti del corso. Terminato il compito scritto, una discussione orale sugli argomenti del compito scritto e su altri argomenti del corso completa l'esame.

Strumenti a supporto della didattica

Software di ottimizzazione

Orario di ricevimento

Consulta il sito web di Valentina Cacchiani

Consulta il sito web di Michele Monaci