Metodi E Modelli Di Ottimizzazione Discreta 1 2017/2018

Programmazione Lineare Binaria, Intera, e Mista: formulazioni ed esempi (Knapsack, Bin Packing, Assegnamento, TSP, Set Covering, Set Partitioning, Set Packing, Matching, Independent Set, Vertex Cover, Localizzazione, Problemi con regione ammissibile non convessa, Problema dei costi fissi, Scheduling, Formulazione di problemi con dei vincoli particolari); Poliedri e Formulazioni, Chiusura Convessa; Limiti al valore della funzione obiettivo: Upper e Lower Bound, Bound di tipo primate e di di tipo duale (rilassamento lineare, ottenuto attraverso la teoria della dualità, combinatorio, Lagrangiano, duality gap); Algoritmi esatti (Ricerca Esaustiva, Totale Unimodularità - CN, CNS - , Branch&Bound, Programmazione Dinamica per Knapsack e per TSP); Algoritmi approssimati (definizione, algoritmo 2-approssimato per TSP, e algoritmo 3/2-approssimato per TSP); Algoritmi euristici (metodi greedy, Ricerca Locale, Ricerca Tabù); cenni di complessità computazionale, difficoltà dei problemi in relazione al tempo necessario per risolverli, problemi polinomiali, problemi NP-completi, Lunghezza stringhe di Input, Ricerca Dicotomica.