Portale di Ateneo - Unibs.it Portale di Ateneo - Unibs.it

Introduzione ai problemi di Ottimizzazione Combinatoria (OC)

Definizione di problema combinatorio. Modelli, proprietà e applicazioni dei problemi di OC. Formulazioni alternative per i problemi di OC. Formulazioni strong e rilassamento continuo. Esempi di formulazioni alternative (problema di albero ricoprente a costo minimo, problema di Perfect Matching). Cenni di Teoria della complessità computazionale. Classificazione degli algoritmi: esatti, euristici, approssimati.

Problemi polinomiali su reti

Reti di flusso: definizioni fondamentali. Totale unimodularità. Problema di Massimo Flusso: modellizzazione e  proprietà. Teorema di massimo flusso-minimo taglio. Algoritmo di Ford-Fulkerson. Applicazioni. Problemi di flusso a costo minimo: proprietà, algoritmi risolutivi e  applicazioni. Problemi di cammino minimo: proprietà, algoritmi risolutivi e applicazioni.

Algoritmi esatti

Algoritmi poliedrali. Metodo di Branch and Bound: proprietà e limiti. Disuguaglianze valide. Problemi di separazione. Metodo di Cutting Planes. Taglio di Gomory e Taglio di Dantzig. Tagli generici e tagli specifici: esempi. Classi di disuguaglianze valide. Algoritmi di separazione esatti e euristici. Applicazione del metodo al problema del commesso viaggiatore e ad un problema di selezione degli indici in un data base relazionale.  Programmazione dinamica deterministica:Principio di ottimalità secondo Bellman. Scomposizione dei problemi in stadi e stati. Ottimizzazione recursiva. Applicazione della metodologia al problema dello zaino binario e al problema di cammino minimo.

Algoritmi euristici e meta-euristici

Algoritmi costruttivi e di miglioramento. Algoritmi di ricerca locale. Algoritmi 2-opt e 3-opt. Metodi Greedy. Meta-euristiche: Tabu Search, Variable Neighborhood Search e Kernel Search. Proprietà dei metodi. Applicazione delle metodologie viste a problemi di node routing e arc routing.

Algoritmi approssimati

Proprietà e caratteristiche dei metodi approssimati. Analisi del caso peggiore. Algoritmo del Tree Algorithm per il problema del commesso viaggiatore. Algoritmo di ordinamento per il problema di maximum independent set. Algoritmo del Next Fit per il problema di bin packing. Algoritmo basato sul rilassamento lineare per il problema di vertex cover. Algoritmi greedy per il problema dello zaino binario.