Dettagli sull'Insegnamento per l'A.A. 2010/2011

Prerequisiti

Conoscenza della Programmazione Lineare e degli Algoritmi di Base

Obiettivi

Apprendere tecniche algoritmiche evolute per alcuni problemi di Ottimizzazione Combinatoria. Capacità di formulare e risolvere problemi di Ottimizzazione Combinatoria come problemi di Programmazione Lineare Intera

Sillabo

• Problemi di Ottimizzazione Combinatoria. Definizioni fondamentali. Esempi: matching (perfetto), insieme stabile, vertex cover, edge cover etc. L'algoritmo (enumerativo) universale e la sua complessità. Disuguaglianze duali deboli. Teorema di Gallai. Teorema di Berge. Algoritmo per il calcolo di un massimo matching su un grafo. Teorema di Konig. L'algoritmo greedy. Problemi di ottimizzazione combinatoria subclusivi. Proprietà di scambio. Matroidi. Teorema di Rado. Matroide vettoriale.
• Ottimalità, rilassamenti e bound. Definizioni di bound “primali” e “duali”. Rilassamento di un problema di programmazione lineare intera. Esempi di rilassamento per il problema del TSP: 1- albero e 2-abbinamento. Algoritmo di Held & Karp per il calcolo dell'1-albero di peso minimo. Bound primali per il TSP: algoritmi approssimati (Double Tree, Christofides). Il problema di Knapsack 0-1: rilassamento lineare e bound primale. Bound per dualità. Formulazioni di problemi di ottimizzazione combinatoria come programmazione lineare intera 0-1 e loro rilassamento lineare.
• Metodi esatti per la risoluzione di problemi di ottimizzazione combinatoria. Algoritmo di Branch-and-Bound. Esempi di problemi di ottimizzazione combinatoria risolti tramite l'algoritmo di Branch-and-Bound: problemi di PLI in due dimensioni, Knapsack 0-1, TSP. Algoritmo di programmazione dinamica per il Knapsack 0-1.
• Matrici totalmente unimodulari. Formulazione ideale per problemi di programmazione lineare intera. Definizione di involucro convesso. Definizione di matrici unimodulari e totalmente unimodulari. Teorema di Hoffman e Kruskal. Condizioni sufficienti di totale unimodularità. Esempio di un problema di programmazione lineare intera con matrice dei vincoli totalmente unimodulare: problema del cammino minimo.
• Introduzione e confronto tra software per la programmazione intera.

Testi di riferimento

• W.J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver, Combinatorial Optimization , Wiley.    
• A. Sassano,, Modelli e Algoritmi della Ricerca Operativa , Franco Angeli Editore.    

Modalità d'esame

Prova scritta ed eventuale orale

Risorse Internet

Aggiornamenti alla pagina del corso

• A.A. 2010/2011
• A.A. 2012/2013
• A.A. 2013/2014
• A.A. 2014/2015
• A.A. 2015/2016
• A.A. 2016/2017
• A.A. 2017/2018
• A.A. 2018/2019
• A.A. 2019/2020