69441 - OPTIMIZATION MODELS AND ALGORITHMS M

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.

Contenuti

Prerequisiti: si richiede una buona conoscenza dell'algebra lineare e della matematica di base.

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

Il corso riguarda lo studio di problemi di ottimizzazione in ambito decisionale e la definizione di modelli matematici e di algoritmi esatti per la loro risoluzione. La teoria matematica su cui si basano i metodi risolutivi viene approfondita con lo studio di teoremi.

Programma

• Introduzione ai problemi di ottimizzazione in ambito decisionale e alla Programmazione Matematica.
• Programmazione convessa, Programmazione Lineare, algoritmo del simplesso, teoria della dualità.
• Programmazione Lineare Intera, algoritmo del branch-and-bound, problemi classici di ottimizzazione combinatoria, rilassamenti, complessità computazionale.
• Modelli di dimensione esponenziale, tecniche di generazione di colonne e separazione di vincoli
• Problemi su grafo, esempi di applicazioni reali, software di ottimizzazione.

Testi/Bibliografia

Slide disponibili su virtuale.unibo.it (alla pagina del corso)

Per approfondimenti:
Fischetti M. Introduction to Mathematical Optimization. Kindle Direct Publishing, 2019.

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 e valutazione dell'apprendimento

L'esame consiste in un compito scritto in cui lo studente risolve alcuni esercizi sugli argomenti visti nel corso (durata circa 60 minuti). Il giorno successivo allo scritto, un esame orale su tutti gli argomenti del corso (inclusi teoremi e dimostrazioni) completa l'esame.

Scritto e orale vanno sostenuti nello stesso appello.

Strumenti a supporto della didattica

Slide disponibili su virtuale.unibo.it (alla pagina del corso) e software di ottimizzazione.

Orario di ricevimento

Consulta il sito web di Valentina Cacchiani