Metodi E Modelli Di Ottimizzazione Discreta 1 2018/2019

Programmazione Lineare Intera, con esempi di formulazioni (tra le altre: Knapsack, Assegnamento, Localizzazione, Scheduling, Set Covering, Set Packing, Set Partitioning). Definizione di un problema di Ottimizzazione Combinatoria con formulazioni: Matching, Independent Set, Node Cover, Bin Packing, circuito hamiltoniano di costo minimo (TSP). Programmazione Mista: modellizzazione di funzioni di costo in presenza di costi fissi, formulazione di problemi con regione ammissibile non convessa. Concetti di poliedro e di formulazione. Bound di tipo primale e di tipo duale (rilassamento lineare, rilassamento attraverso la teoria della dualità, rilassamento combinatorio, rilassamento lagrangiano). Algoritmi esatti: Ricerca Esaustiva, Totale Unimodularità, Programmazione Dinamica (per Knapsack e per TSP), Branch&Bound. Algoritmi approssimati: 2 algoritmi approssimati per TSP. Algoritmi euristici: Greedy, Ricerca Locale, Ricerca Tabù. Cenni di complessità computazionale.