Algoritmi E Modelli Per L'ottimizzazione Discreta 2023/2024

AMOD è un corso magistrale sulla teoria e le applicazioni dell'ottimizzazione discreta. Dopo una prima parte dedicata alla ricapitolazione di nozioni di programmazione lineare e metodo del simplesso, trattiamo in modo più approfondito la programmazione lineare intera (PLI) e intera mista con alcuni riferimenti a problemi su reti. Metodi per la PLI: tagli di Gomory, metodi di enumerazione implicita: branch and bound e branch and bound "combinatori", Programmazione Dinamica. Concetto di formulazione di un PLI e sua qualità. Formulazioni compatte e non. Descrizioni esplicite ed implicite di un poliedro. Metodi di generazione colonne (problemi di pricing) e generazione vincoli (oracolo di separazione). Esempi: Cutting Stock, Shortest (s,t)-path. Rilassamento di un problema di ottimizzazione intera (lagrangiano, surrogato ecc.) Esempi. Algoritmi approssimati: concetti base. Esempi: Vertex-Cover, TSP euclideo. Metodi primali-duali: Esempio: Vertex-Cover. Algoritmi randomizzati per problemi deterministici di ottimizzazione discreta. Casi di studio: Facility Location e metodi di ascesa duale. Vehicle Routing: formulazioni ed euristici. Ottimizzazione su reti di flusso: problemi di flusso a costo minimo, simplesso su reti.