Metodi E Modelli Di Ottimizzazione Discreta 1 + 2 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.

Richiami di teoria dei grafi. Modelli di set covering, partitioning e packing. Problemi di colorazione su grafi. Problemi di localizzazione