Sillabo dell'insegnamento

• MAT - Crediti di MATEMATICA
MAT/09 - Ricerca Operativa
Teorema Max-Flow/Min-Cut; Algoritmi basati su cammini aumentanti; Shortest augmenting path; Algoritmi push-relabel; Applicazioni dei problemi di massimo flusso e taglio minimo
MAT/09 - Ricerca Operativa
Problemi di Massimo Flusso
MAT/09 - Ricerca Operativa
Problemi di cammino minimo con pesi qualsiasi; Algoritmo di Ford; Algortmo di Ford-Bellman
MAT/09 - Ricerca Operativa
Applicazioni a problemi di telecomunicazioni: Assegnamento di frequenze; Progetto di reti; Flusso multicommodity; Alberi ricoprenti con vincoli aggiuntivi
MAT/09 - Ricerca Operativa
Dualità lagrangiana: Rilassamento lagrangiano; Euristiche lagrangiane Euristiche basate su formulazioni MIP: Dive-and-Fix, Relax-and-Fix, Cut-and-Fix; Local branching, feasibility pump, RINS
MAT/09 - Ricerca Operativa
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
MAT/09 - Ricerca Operativa
Ottimalità, rilassamenti e bound 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; Tool software
MAT/09 - Ricerca Operativa
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
MAT/09 - Ricerca Operativa
Formulazioni di problemi interi e binari; Problema di assegnamento; 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
MAT/09 - Ricerca Operativa
Applicazioni dei problemi di flusso a costo minimo
MAT/09 - Ricerca Operativa
Problemi di taglio minimo su grafi non orientati; Algoritmo Node Identification; Algoritmo Random Contraction
MAT/09 - Ricerca Operativa
Problemi di Flusso a Costo Minimo; Algoritmi primali: algoritmo del circuito aumentante; Simplesso su reti