Ottimizzazione Combinatoria: Laboratorio

(Corso di Laurea in Informatica (quinquennale))

Codice:

4I085

Crediti:

Semestre:

Sigla:

OCL

Docente

Maria Grazia Scutellà

Tel. 0502212771

Prerequisiti

Ottimizzazione Combinatoria

Obiettivi di apprendimento

Presentare ed esemplificare le principali tecniche algoritmiche in Ottimizzazione Combinatoria applicandole ad un problema specifico.

Descrizione

Obiettivo del corso è illustrare alcune delle principali tecniche algoritmiche per la risoluzione di problemi di Ottimizzazione Combinatoria.

Il corso utilizzerà come "filo conduttore" un importante problema di Ottimizzazione Combinatoria (diverso di anno in anno), e le principali tecniche algoritmiche saranno presentate ed esemplificate facendo riferimento a tale problema.

English Description

The course is intended to allow the students to experience on the application of various combinatorial optimization techniques. A "leading" problem is choosen (different every year) to which the techniques are applied, up to obtaining one (or more) complete solution approach.

Programma

Introduzione (2 ore)
Presentazione del "filo conduttore" dell'anno in corso: il Problema dell'Albero di Copertura di Costo Minimo Capacitato (CMSA), un importante problema di "network design".
Rilasciamenti I (8 ore)
Vengono presentati algoritmi per due immediati rilasciamenti del problema: il Problema dell'Albero di Copertura di Costo Minimo nel caso non orientato (MST) e nel caso orientato (MSA).
Rilasciamenti II (10 ore)
Vengono presentate diverse formulazioni di Programmazione Lineare Intera per il (CMSA), e vengono descritte tecniche per la risoluzione (di opportuni rilasciamenti) del rilasciamento lineare.
Euristiche (10 ore)
Vengono introdotte euristiche di diversa natura per l'individuazione di una "buona" soluzione ammissibile per il problema in esame.
Algoritmi Enumerativi (10 ore)
Tutte le componenti precedentemente descritte vengono utilizzate per la progettazione di un algoritmo "Branch and Bound" per il calcolo di una soluzione ottima del problema.

Ore lezione:

Ore esercitazione:

Bibliografia

Articoli distribuiti dal docente durante il corso.