Dettagli sull'Insegnamento per l'A.A. 2015/2016
Nome:
Network Optimization / Network Optimization
Informazioni
Crediti:
: Master Degree in Computer Science 6 CFU (c)
Erogazione:
Master Degree in Computer Science 1st anno curriculum SEAS Compulsory
Lingua:
Inglese
![[info]](img/info16.png)
Prerequisiti
Conoscenze di base di:
Matematica discreta, Programmazione Lineare, Algoritmi e Strutture dati, Complessità Computazionale.
Conoscenza di almeno un linguaggio di programmazione.
Obiettivi
Capacità di individuare e formulare problemi di ottimizzazione su reti come problemi di Programmazione Lineare Intera.
Conoscenza delle tecniche algoritmiche fondamentali per la risoluzione dei problemi di Programmazione Lineare Intera.
Conoscenza dei principali strumenti software per la risoluzione di problemi di Programmazione Lineare Intera
Sillabo
- Formulazioni di problemi interi e binari; Problema di assegnamento; Problema del Massimo Insieme Stabile: Set Covering, Packing e Partitioning; Minimo albero ricoprente; Problema del commesso viaggiatore (TSP); Formulazione di condizioni logiche
- Formulazioni Intere Miste: Modellazione di costi fissi; Problema di localizzazione di impianti; Problema di lot-sizing, Problemi con insiemi finiti di alternative, Problemi disgiuntivi.
- Ottimalità, rilassamenti e bound. Geometria di R^n: Spazi lineari e affini; Poliedri: dimensione, rappresentazioni, disuguaglianze valide, facce, vertici e facce massimali; Formulazioni alternative e formulazioni estese; Gerarchia di formulazioni e formulazione ideale
- Algoritmo di branch-and-bound basato sul rilassamento lineare: Preprocessamento, Strategie di branching, Strategie per la selezione del nodo e della variabile di branching, Euristiche primali.
- Algoritmo del piano di taglio e algoritmo di branch-and-cut: Tagli di Chvatal-Gomory: definizione e procedura di separazione; Algoritmo del piano di taglio; Disuguaglianze valide forti. Disuguaglianze cover, clique e disuguaglianze per l'eliminazione dei subtour. Algoritmo di branch-and-cut.
- Tool software per la Programmazione Lineare Intera
- Dualità lagrangiana: Rilassamento lagrangiano; Euristiche lagrangiane
- Problemi su reti: formulazioni e algoritmi. Minimo albero ricoprente con vincoli, Problemi di cammino minimo vincolato, Problemi di flusso multicommodity, Problema del Commesso viaggiatore (simmetrico e asimmetrico), problema di vehicle routing, problema dell'albero di Steiner, problema di Progetto di Reti.
- Euristiche per problemi su reti. Local search, tabu search, simulatead annealing. Euristiche basate sulle formulazioni MIP.
Descrittori di Dublino
Alla fine del corso, lo studente dovrebbe
- Conoscere e definire i principali problemi di ottimizzazione su reti con obiettivo singolo
- Utilizzare e progettare algoritmi esatti o euristici per risolvere problemi di ottimizzazione su reti con singola funzione obiettivo
- Saper identificare le appropriate metodologie per modellare e risolvere problemi di ottimizzazione su reti
- Saper spiegare le scelte modellistiche e la complessità computazionale richieste per risolvere problemi di ottimizzazione su reti
- Apprendere le tecniche algoritmiche stato dell'arte per problemi di ottimizzazione su reti
Testi di riferimento
- L.A. Wolsey, Integer Programming , Wiley. 1998.
Modalità d'esame
Prova scritta e progetto
Aggiornamenti alla pagina del corso
Le informazioni sulle editioni passate di questo corso sono disponibili per i seguenti anni accademici:
Per leggere le informazioni correnti sul corso, se ancora erogato, consulta il catalogo corsi di ateneo.
Ultimo aggiornamento delle informazioni sul corso: 10 settembre 2015, 10:40
English version
sad
strutture.univaq