Dettagli sull'Insegnamento per l'A.A. 2017/2018

Prerequisiti

Conoscenza degli algoritmi di base, nozioni di algebra lineare, programmazione lineare

Obiettivi

Apprendere tecniche algoritmiche per alcuni problemi di Ottimizzazione Combinatoria. Saper formulare e risolvere problemi di Ottimizzazione Combinatoria come problemi di Programmazione Lineare Intera. Conoscere la complessità dei problemi studiati.

Sillabo

• Prerequisiti: grafi, definizioni e proprietà fondamentali. Elementi di teoria della complessità computazionale. Esempi. Problemi di Ottimizzazione Combinatoria. Definizioni fondamentali. Esempi: trasversale (vertex-cover), insieme stabile, insieme dominante, edge-cover, matching (perfetto), knapsack, colorazione di un grafo (numero e indice cromatico), cammino minimo, sottografo ricoprente etc. Formulazioni come programmazione lineare 0-1.
• Matrici unimodulari e totalmente unimodulari. Condizioni necessarie e condizioni sufficienti. Teorema di Hoffmann-Kruskal. Involucro convesso e formulazione ideale di un problema di PL intera. Esempi: cammino minimo, flusso a costo minimo, matching bipartito, grafi intervallo.
• Cammini su grafi diretti aciclici (DAG) e programmazione dinamica. Esempi di applicazione: cammini ottimi su DAG, knapsack 0-1. [Proiezione di poliedri, sistemi di disequazioni lineari, Teorema di Fourier-Veronese, metodo di Fourier-Motzkin. Richiami di teoria della dualità nella programmazione lineare. Metodo primale duale. Esempio di applicazione: Metodo di Dijkstra].
• Matroidi. Algoritmo Greedy. Definizione e caratterizzazione di un matroide (Teorema di Rado). Richiami di algebra lineare: dipendenza e indipendenza lineare, basi, unicità della rappresentazione, Teorema di Steinitz o dello scambio. Esempi: matroide banale, matroide grafico, matroide partizione, matroide vettoriale, [matroide matching]. Rappresentazione di matroidi. [Un applicazione industriale]. [Funzione rango, funzioni submodulari e supermodulari. Rango di un matroide. Funzione di supporto di un insieme convesso. Poliedro submodulare. Estensione di Lòvasz. Poliedro di un matroide, intersezione di matroidi, intersezione di due poliedri submodulari].
• Algoritmi ad approssimazione garantita. Definizioni. Schemi polinomiali di approssimazione (PTAS, EPTAS, FPTAS). Esempi: TSP: double tree and Christofides; Knapsack 0-1.
• Matching (perfetto/non perfetto, pesato/non pesato, bipartito/non bipartito). Diseguaglianze duali deboli: trasversale, numero di stabilità, edge-cover e matching. Il caso bipartito: Teoremi di Gallai e König. [Matrici bistocastiche e matching bipartito perfetto. Matching generale: poliedro del matching, Teorema di Edmonds].
• Rilassamento lineare di un problema di programmazione lineare (mista) intera. Enumerazione implicita: metodo di branch-and-bound. Bound lineari, esempio: Knapsack intero, Knapsack 0-1. Dicotomia su una variabile frazionaria. Bound combinatorici, esempio: TSP.
• [Separazione di un poliedro intero. Cenni sul Metodo dell'Ellissoide. Separazione e ottimizzazione: Generazione di diseguaglianze valide. Soluzione di PL con un numero esponenziale di disequazioni, esempi: Taglio minimo, TSP, Knapsack 0-1, Insieme Stabile].

Descrittori di Dublino

Alla fine del corso, lo studente dovrebbe

Testi di riferimento

• W.J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver, Combinatorial Optimization , Wiley. 1997.    
• C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity , Dover Books on Computer Science. 1998. ISBN-13: 978-0486402581, price: used from $6.24, new from $11.51 http://www.amazon.com/Combinatorial-Optimization-Algorithms-Complexity-Computer/dp   
• / A. Sassano,, Modelli e Algoritmi della Ricerca Operativa , Franco Angeli Editore.    

Modalità d'esame

Prova scritta e orale

Note

• Nel semestre di erogazione del corso il docente riceve gli studenti per spiegazioni ogni giovedì dalle 14:30 alle 15:30

Risorse Internet

Aggiornamenti alla pagina del corso

• A.A. 2016/2017
• A.A. 2017/2018
• A.A. 2018/2019
• A.A. 2019/2020