1. Introduzione ai problemi di Ottimizzazione Combinatoria (OC). Definizione di problema combinatorio. Modelli, proprietà e applicazioni dei problemi di OC. Formulazioni alternative per problemi di OC. Formulazioni strong e rilassamento continuo; Convex Hull. Esempi di formulazioni alternative (problema di albero ricoprente a costo minimo, problema di
Perfect Matching).
2. 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.
3. Introduzione ai problemi di Arc e Node Routing. Proprietà e differenze. Condizioni necessarie e sufficienti per grafi euleriani. Problema del Chinese Postman Problem. Complessità del problema. Problema del Rural Postman Problem. Complessità e casi particolari. Algoritmi risolutivi. Capacitated Arc Routing Problem: proprietà e formulazione matematica.
4. Algoritmi euristici e meta-euristici.
Algoritmi costruttivi e di miglioramento. Algoritmi di ricerca locale. Esempi: algoritmi 2-opt e 3-opt per il problema del commesso viaggiatore. Metodi Greedy. Meta-euristiche: Tabu Search, Variable Neighborhood Search, Adaptive Large Neighborhood Search e Kernel Search. Proprietà dei metodi. Applicazione delle metodologie viste a problemi di node routing e arc routing.
5. Algoritmi esatti.
Algoritmi poliedrali. Metodo di Branch and Bound: proprietà e limiti. Disuguaglianze valide e problemi di separazione. Metodo di Cutting Planes. Taglio di Gomory e Taglio di Dantzig. Tagli generici e tagli specifici: esempi. Classi di disuguaglianze valide e 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.
6. 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.
7. Ottimizzazione Bilivello. Definizione e proprietà. Classi di problemi. Metodologie risolutive.