Combinatorial Optimization
Titolo insegnamento in inglese: Combinatorial Optimization
Lingua: italiano
Anno di corso: 2
Semestre: 2
CFU: 6
Insegnamenti propedeutici previsti: Nessuno.
Docenti:
- Paola Festa
Obiettivi Formativi
Questo insegnamento si prefigge quale obiettivo principale l'introduzione degli studenti all'uso dei modelli di programmazione matematica con particolare attenzione rivolta ai modelli di ottimizzazione a variabili intere. Allo studio teorico di questi problemi viene affiancata la descrizione delle loro applicazioni in scenari del mondo reale, inclusi il controllo ottimo, le comunicazioni, la logistica, i servizi e la produzione industriale. 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: definizioni di problema di ottimizzazione e di problemi di decisione; definizione di un generico problema di ottimizzazione combinatoria lineare; definizione di un generico problema di ottimizzazione combinatoria non lineare; proprietà della regione ammissibile di un problema di ottimizzazione combinatoria. Funzioni di Karpriducibilità polinomialmente calcolabili. Classi di Complessità Computazionale: classe P e sue proprietà; classe NP e sue proprietà; classe NP-ardua e sue proprietà; classe NP-completa e sue proprietà; classe fortemente NP-completa e sue proprietà. Classificazione dei metodi di soluzione: metodi esatti; metodi approssimazione; metodi euristici. Metodi esatti: Upper e Lower Bounds; Branch & Bound; Branch & Cut; Piani di Taglio; Programmazione Dinamica. Fondamenti teorici per i metodi greedy – Teoria delle Matroidi: definizione di matroide e sue proprietà; algoritmi greedy per problemi su matroidi pesate e dimostrazione delle loro correttezza; esempi di problema di ottimizzazione combinatoria risolvibili all’ottimo tramite tecnica greedy in quanto riconducibili a problemi su matrodi pesate: il Problema dell’Albero di Copertura Minimo di un grafo; un Problema di Schedulazione. Algoritmi di Approssimazione: definizione e calcolo del rapporto di prestazione nel caso peggiore (errore assoluto) di un algoritmo di approssimazione; definizione di errore relativo nel caso peggiore di un algoritmo di approssimazione. Classi di Approssimazione: classe APX e sue proprietà; classe PTAS e sue proprietà; classe FPTAS e sue proprietà. Problema del Vertex Cover Minimo di un grafo: descrizione verbale e logico-matematica; teorema dell’approssimabilità; un algoritmo di approssimazione di tipo greedy: dimostrazione della convergenza; calcolo dell’errore; analisi della complessità computazionale; un algoritmo di approssimazione di tipo random: dimostrazione della convergenza; calcolo dell’errore; analisi della complessità computazionale. Problema del Massimo Insieme Indipendente di un grafo: descrizione verbale e logico-matematica; teorema dell’inapprossimabilità; un algoritmo di tipo greedy non di approssimazione: dimostrazione della convergenza; calcolo dell’errore; analisi della complessità computazionale. Classificazione dei Metodi Euristici. Definizione di Neighborhood di una soluzione. Procedure di Ricerca Locale. Algoritmi Metaeuristici: algoritmi genetici; algoritmi tabù search; algoritmi simulated annealing; algoritmi GRASP (Greedy Randomized Adaptive Search Procedure): un algoritmo GRASP per il Problema Max-Cut. Il Problema dello Zaino 0/1: descrizione verbale e logico-matematica; rilassamento continuo: il Problema dello Zaino Frazionario; un algoritmo Branch & Bound; due algoritmi di Programmazione Dinamica; due upper bounds; un algoritmo 1/2 approssimato: dimostrazione della convergenza; calcolo dell’errore; analisi della complessità computazionale; un PTAS: dimostrazione della convergenza; calcolo dell’errore; analisi della complessità computazionale; un FPTAS: dimostrazione della convergenza; calcolo dell’errore; analisi della complessità computazionale; Il Problema del Commesso Viaggiatore (TSP): descrizione verbale e logico-matematica; teorema dell’inapprossimabilità; un algoritmo Branch & Bound; varianti del Problema dello Commesso Viaggiatore (TSP): TSP su grafi generici; TSP grafico; TSP asimmetrico; TSP bottleneck. un algoritmo 2approssimato per il TSP simmetrico con disuguaglianza triangolare: dimostrazione della convergenza; calcolo dell’errore; analisi della complessità computazionale; un algoritmo 3/2-approssimato per il TSP simmetrico con disuguaglianza triangolare: dimostrazione della convergenza; calcolo dell’errore; analisi della complessità computazionale; algoritmi euristici per il TSP standard; algoritmi di costruzione di una soluzione ammissibile per il TSP standard; insiemi neighborhoods di una soluzione; algoritmi di ricerca locale: 2-opt exchange; k-opt exchange; analisi della complessità computazionale di 2-k-opt exchange. Metaeuristiche per il TSP standard: un algoritmo genetico; un algoritmo tabù search; un algoritmo simulated annealing; un algoritmo GRASP.
Modalità didattiche
Lezioni frontali. Esercitazioni.
Materiale didattico
Appunti e Dispense del Corso.
P. Festa. Ottimizzazione Combinatoria, UTET Università – De Agostini Scuola, 2017.
Modalità di esame
L'esame si articola in prova aolo orale.