Home » Archivo » Archvio 2013 » METODI E MODELLI PER L'OTTIMIZZAZIONE COMBINATORIA - 2013/2014

Laurea Magistrale

Salta il menu di secondo livello

METODI E MODELLI PER L'OTTIMIZZAZIONE COMBINATORIA - 6 CFU - A.A. 2013/2014

Insegnante

Dott. Luigi De Giovanni

Periodo

II Anno - 1 Trimestre | 01/10/2013 - 07/12/2013

Ore: 48 (4 esercitazione, 12 laboratorio, 32 lezione)

Torna su ▲

Prerequisiti

Elementi di ricerca operativa, elementi di programmazione lineare, elementi di base di programmazione.

Conoscenze e abilità da acquisire

Uso di metodologie avanzate di supporto alle decisioni per la modellazione e la soluzione di problemi di ottimizzazione
combinatoria. Il corso intende fornire strumenti matematici e algoritmici per la soluzione di problemi pratici di ottimizzazione con l'utilizzo dei pacchetti software e delle librerie di ottimizzazione più diffusi.

Modalità di esame

Esame orale sui contenuti del corso. Realizzazione facoltativa di un progetto individuale sulla soluzione di un problema, reale o realistico, di ottimizzazione combinatoria (definizione del problema, modellazione, applicazione di un metodo di soluzione esatto e/o euristico).

Criteri di valutazione

L'esame verifica il livello di apprendimento degli argomenti svolti e la capacità dello studente di applicarli per la soluzione di problemi reali di ottimizzazione combinatoria.

contenuti

1. Approfondimenti e applicazioni di Programmazione Lineare e dualità : metodo del simplesso primale-duale, tecniche di generazione di
colonne, applicazioni a problemi di ottimizzazione su grafo.

2. Metodi avanzati di Programmazione Lineare Intera (PLI): Branch & Bound e tecniche di rilassamento, formulazioni alternative di
modelli PLI, metodo dei piani di taglio e tecniche di Branch & Cut, applicazioni ad esempi notevoli: commesso viaggiatore, problemi di
localizzazione, problemi di network design etc.

3. Meta-euristiche di Ottimizzazione Combinatoria: ricerca di vicinati e varianti, algoritmi evolutivi.

4. Applicazione di metodi di modellazione e ottimizzazione su grafo.

5. Laboratori: utilizzo di software e librerie di ottimizzazione.

Attività di apprendimento previste e metodologie di insegnamento

L'insegnamento prevede lezioni frontali, esercitazioni in laboratorio e discussione di esempi notevoli. Le esercitazioni in laboratorio consistono nell'implementazione di algoritmi di ottimizzazione combinatoria sia esatti (con l'uso di librerie di programmazione lineare intera) sia euristici).

Eventuali indicazioni sui materiali di studio

Dispense fornite dal docente. Articoli scientifici.

Testi di riferimento

Torna su ▲