Programmazione Intera e Ottimizzazione Combinatoria 23-24
Schedule: lun 15-17, mar 16-19, mer 13-15, ven 14-17
dal 26/02/2024 al 31/05/2024
Aula: Aula 1 SPV, Edificio RM031
Meet: https://meet.google.com/dfw-qzjj-ttk
Google Classroom: ky7pnda
Breve descrizione:
Il corso di Programmazione Intera e Ottimizzazione Combinatoria (codice 10600452) viene erogato all'interno dell'offerta formativa del primo anno della laurea di secondo livello in Ingegneria Gestionale. Il corso, per un totale di 120 ore di didattica frontale (12 CFU), ha lo scopo di completare la preparazione dellə studentə sulle tematiche di ottimizzazione. Naturali prerequisiti per questo corso sono gli argomenti di base della Ricerca Operativa, Ottimizzazione Combinatoria e su Reti.
Corso
Ulteriori informazioni riguardo il corso sono reperibili sul sito del Prof. Fabio Furini.
Programma delle esercitazioni
Il corso è volto ad approfondire argomenti tipici dei problemi di programmazione intera e dell' ottimizzazione combinatoria.
Il programma verte sui seguenti temi:
I Richiami: Norma e valore asoluto, Sistemi di equazioni lineari, Sommatorie, Principio di induzione, Insiemi convessi, Funzioni lineari, Poliedri.
II Funzioni Quadratiche, Ottimi locali e globali, Programmazione Lineare.
III Metodo del Simplesso, Metodo del Simplesso Rivisto, Prima Fase del Metodo del Simplesso.
IV Problema Primale e Duale. Condizioni di Complementarità. Metodo del Simplesso Duale.
V Programmazione Lineare Intera. Implicazioni Logiche. Forma Normale Congiuntiva.
VI Tagli di Gomory.
VII Metodo del Branch & Bound. Strategie di Branching. Variable e Node Selection.
VIII Knapsack Problem. Un algoritmo di Branch & Bound. Dantzig upper bound. Martello-Toth upper bound.
IX Cover inequalities. Problema di separazione delle cover inequalities. Cover inequalities estese.
X Notazioni asintotiche e proprietà. Funzioni polinomiali. Classi di crescita.
XI Analisi degli algoritmi. Correttezza e tempi di calcolo degli algoritmi.
XII Programmazione Dinamica.
Esame
L’esame è scritto e si svolge senza ausilio di materiale didattico e consiste in 3 possibili tipologie di esercizio che coprono tutti gli argomenti trattati a lezione. La prima tipologia riguarda la modellistica e le proprietà dei modelli ILP, la seconda tipologia riguarda gli aspetti algoritmici e la terza tipologia gli aspetti metodologici e teorici.
La durata dell'esame (approssimativamente 2 ore) e la sua composizione può variare di volta in volta.
Il voto complessivo per la prova si ottiene sommando le valutazioni dei singoli quesiti, se il totale supera il punteggio di 30 viene assegnata la lode.
Per sostenere l’esame è tassativamente necessaria la prenotazione su INFOSTUD, non sono previste eccezioni.
Materiale
Tutto il materiale didattico è disponibile nella cartella condivisa di Google Classroom.
Testi per approfondimenti:
"Ricerca Operativa" di Silvano Martello
"Introduction to Mathematical Optimization" di Matteo Fischetti
"Linear Programming" di Vasek Chvatal,
"Integer Programming" di Laurence Wolsey
"Integer Programming" di Michele Conforti , Gérard Cornuéjols , Giacomo Zambelli
"Introduction to Linear Optimization" di Dimitris Bertsimas e John Tsitsiklis.
"Introduction to Algorithms" di Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein
Docenti
fabio.furini@uniroma1.it*
Via Ariosto 25, 00185, Roma
06-77274097
Room A109
annalivia.croella@uniroma1.it*
Via Ariosto 25, 00185, Roma
06-77274099
Room A102