Metodi E Modelli Di Ottimizzazione Discreta 1 2017/2018

Concetti di poliedro e di 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, node cover, edge cover, vertex coloring, edge coloring di un grafo. Il problema del circuito hamiltoniano di costo minimo (TSP). Algoritmi euristici: Greedy, Ricerca Locale, Tabu Search. Algoritmi approssimati: algoritmo di Christofides per il TSP. Algoritmi esatti: totale unimodularita' delle matrici, programmazione dinamica, branch-and-bound. Bound di tipo primale e di tipo duale; rilassamenti ottenuti attraverso la teoria della dualità. Rilassamento lagrangiano. Cenni di complessità computazionale.