Programma di Metodi E Modelli Di Ottimizzazione Discreta 1 :
Concetti di poliedro, formulazione. Il problema dell'ottimizzazione e quello della separazione. La programmazione lineare intera. Esempi di formulazioni: knapsack, assegnamento, localizzazione, modellizzazione di funzioni di costo in presenza di costi fissi, scheduling, coloring, set covering, set packing. Definizione di un problema di ottimizzazione combinatoria. Problemi del matching, stable set, vertex cover, edge cover in un grafo. Il problema del commesso viaggiatore. Algoritmi euristici: Greedy, Ricerca Locale, Tabu Search. Algoritmi approssimati: due esempi per il TSP. Algoritmi esatti: totale unimodularita' delle matrici, algoritmi di prommazione dinamica per il knapsack e per il TSP, branch-and-bound. Bound di tipo primale e di tipo duale; rilassamenti ottenuti attraverso la teoria della dualita'. Rilassamento lagrangiano. Cenni di complessita' computazionale.
Risultati di apprendimento previsti: Conoscenza dei principali modelli di formulazione della Programmazione Lineare a Numeri Interi e dell'Ottimizzazione Combinatoria. Capacita' di definire nuove formulazioni di PLI. Conoscenza degli algoritmi (euristici, esatti, e approssimati) per la soluzione di problemi di PLI e capacita' di scelta in relazione al problema e alla sua complessita' computazionale.
Eventuali propedeuticita': si assume che lo studente abbia padronanza dell'algebra, della geometria, della programmazione e di quanto previsto dall'insegnamento di Ricerca Operativa.
Testi di riferimento: dispense fornite dal docente
English
Italiano