Algoritmi e Modelli di Ottimizzazione

La pagina ufficiale del corso con tutto il materiale didattico (dispense, esercizi, compiti d'esame, ecc.) è disponibile su https://ingegneriacivileinformaticatecnologieaeronautiche.el.uniroma3.it/

Orario delle lezioni: Lunedì e Venerdì mattina

Modalità di Esame: L'esame consiste in una prova scritta al termine del corso, secondo il calendario indicato. Gli studenti che riportano un voto quasi sufficiente, o che desiderano discutere lo scritto, integrano l'esame con una prova orale da sostenersi nello stesso appello.

L'esame per gli appelli successivi al primo (appelli di recupero) consiste in una prova scritta e orale.

Programma del corso

Introduzione alla Programmazione Lineare a numeri interi (PLI): Relazione fra PL e PLI, formulazioni equivalenti, rilassamenti, matrici totalmente unimodulari, tecniche standard per la formulazione di problemi di PLI.

Formulazione di tipici problemi di ottimizzazione: Localizzazione di impianti, Scelta di investimenti, Sequenziamento di attività, Ottimizzazione su reti, Trasporti, Set covering, Set Partitioning, Set Packing, Turni del personale, Cloud Computing.

Soluzione esatta di problemi di Programmazione Lineare a numeri interi: Programmazione Dinamica,Branch and Bound, Piani di taglio, cenni al Branch and Cut.

Problemi su grafi: Max Matching, Min Vertex Cover. Grafi euleriani e grafi bipartiti.

Utilizzo di un software commerciale per la soluzione di problemi di programmazione matematica.

Testi di riferimento:

[1] M. Fischetti, "Lezioni di Ricerca Operativa", Edizioni Libreria Progetto Padova, Italia, 1995. (Cap. 2, 5, parte del 6 e del 7).

[2] R. Ahuja, T. Magnanti, J. Orlin, "Network Flows", Prentice Hall, 1993. (pg. 189-191, 473-475, 494-496)

[3] Dispense fornite dal docente e/o disponibili sul web.