SITE TITLE

LOGO DIETI

Ottimazione combinatoria

Titolo insegnamento in inglese: 

Combinatorial Optimization

 Lingua: italiano

Insegnamento: Ottimizzazione combinatoria

Anno di corso: II

CFU: 6

SSD: MAT/09

Ore di lezione: 48

Semestre: 2

Modulo: Nessuno

Codice: 26266-26429

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.

 

Contenuti:

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 Karp-riducibilità 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 2-approssimato 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.

 

Propedeuticità: Ricerca operativa

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

 

 

 

 

 

 

Solo orale

 

 

 

 

 

 

 

 

 

 

In caso di prova scritta i quesiti sono 

     

 

     

 

Altro

 

 

Docente: Festa Paola