Ottimizzazione Combinatoria

Crediti

Propedeuticità

Nessuna.

Settore scientifico-disciplinare

MAT/09 Ricerca Operativa.

Modalità dell’esame

Prova orale e valutazione dell’attività di laboratorio.

Obiettivi
formativi

Questo insegnamento si prefigge quale obiettivo principale l’introduzione degli studenti all’uso dei modelli di programmazione matematica sia lineare che non lineare con particolare attenzione rivolta ai modelli di ottimizzazione a variabili intere. Per quanto riguarda i modelli di programmazione a variabili intere con regione ammissibile finita (problemi combinatorici sia lineari che non lineari), il corso mira a fornire un trattamento completo e rigoroso della loro classificazione computazionale. Per quei problemi computazionalmente intrattabili, oltre ai metodi di soluzione esatti, il corso si prefigge di illustrare anche metodi più sofisticati, come algoritmi di approssimazione e algoritmi euristici e metaeuristici.

Programma

Introduzione all’Ottimizzazione Combinatoria. Funzioni di Karp-riducibilità polinomialmente calcolabili. Classi di Complessità Computazionale. Classificazione dei metodi di soluzione. Programmazione Dinamica. Fondamenti teorici per i metodi greedy: Teoria delle Matroidi. Algoritmi di Approssimazione. Classi di Approssimazione. Problema del Vertex Cover Minimo di un grafo. Problema del Massimo Insieme Indipendente di un grafo. Classificazione dei Metodi Euristici. Definizione di Neighborhood di una soluzione. Procedure di Ricerca Locale. Algoritmi Metaeuristici: Il Problema dello Zaino 0/1 e del Commesso Viaggiatore (TSP); teorema dell’inapprossimabilità; un algoritmo Branch & Bound; varianti del TSP. Algoritmi per il TSP. Insiemi neighborhoods di una soluzione; algoritmi di ricerca locale. analisi della complessità computazionale di 2-k-opt exchange. Metaeuristiche per il TSP standard.

Risultati dell’apprendimento
attesi

Al termine dell’insegnamento, lo studente deve dimostrare di

comprendere e conoscere le formalizzazione dei modelli di ottimizzazione (lineare e nonlineare) per problemi di programmazione a variabili intere, con particolare riferimento a quelli caratterizzati da regione ammissibile finita, nonché la conoscenza della teoria e dei metodi di ottimizzazione intera (lineare e non lineare);
saper applicare le conoscenze acquisite nella corretta modellizzazione di un problema di ottimizzazione combinatoria e nella corretta sua soluzione ottenuta dalla scelta del miglior metodo;
saper comunicare in maniera chiara, rigorosa ed efficace idee e soluzioni a interlocutori specialisti e non specialisti;
saper individuare i metodi più appropriati per analizzare e risolvere un problema inerente gli argomenti del corso e interpretare correttamente i risultati.

Risultati di apprendimento
che si intende verificare

Verifica della abilità nella risoluzione di esercizi di varia difficoltà; chiarezza, correttezza e completezza nell’esposizione scritta e orale degli argomenti inerenti l’insegnamento.

Ottimizzazione Combinatoria