Combinatorial optimization

A.A. 2021/2022
6
Crediti massimi
48
Ore totali
SSD
MAT/09
Lingua
Inglese
Obiettivi formativi
L'obiettivo dell'insegnamento è di approfondire la conoscenza degli algoritmi di complessità polinomiale per calcolare la soluzione ottima di classici problemi di ottimizzazione combinatoria su grafo.
Risultati apprendimento attesi
Capacità di progettazione di algoritmi per risolvere in modo efficiente problemi di ottimizzazione combinatoria polinomiali su grafo
Programma e organizzazione didattica

Edizione unica

Responsabile
Periodo
Primo semestre
In relazione alle modalità di erogazione delle attività formative per l'a.a. 2021/22, verranno date indicazioni più specifiche nei prossimi mesi, in base all'evoluzione della situazione sanitaria.
Programma
Richiami di programmazione lineare e teoria della dualità.
· Grafi, definizioni, proprietà. Componenti connesse, algoritmi di visita di grafi.
· Alberi e arborescenze. Minimum cost spanning tree: Kruskal, Prim, Boruvka algorithms. Minimum cost spanning arborescence: Edmonds algorithm.
· Cammini minimi. Unweighted graphs: BFS algorithm. Weighted acyclic graphs: Critical Path Method. Grafi senza cicli negativi: Bellman-Ford algorithm. Grafi senza archi negativi: Dijkstra algorithm. Algoritmo di Floyd-Warshall per il calcolo degli all-pairs shortest paths.
· Flussi ottimi. Algoritmo di Ford-Fulkerson per il problema di massimo flusso. Algoritmi per Il problema di massimo flusso a minimo costo. Dualità: max flow - min cut. Algoritmo di Gomory e Hu per trovare il minimo taglio in un grafo pesato.
· Matching bipartito. Algoritmo ungherese.
· Trasporto a costo minimo. Algoritmo di Dantzig.
Prerequisiti
Ricerca operativa
Metodi didattici
Lezioni frontali
Materiale di riferimento
R.K. Ahuja, T.L. Magnanti, J.B. Orlin "Network flows", Prentice Hall, 1993
Modalità di verifica dell’apprendimento e criteri di valutazione
Prova scritta, progetto e prova orale, oppure presentazione di articolo scientifico e prova orale.
MAT/09 - RICERCA OPERATIVA - CFU: 6
Lezioni: 48 ore
Docente/i
Ricevimento:
su appuntamento
via Celoria 18, terzo piano