Dettagli sull'Insegnamento per l'A.A. 2010/2011

Sillabo

• 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
• 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
• 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
• 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
• 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
• Applicazioni a problemi di telecomunicazioni: Assegnamento di frequenze; Progetto di reti; Flusso multicommodity; Alberi ricoprenti con vincoli aggiuntivi

Testi di riferimento

• L.A. Wolsey, Integer Programming , Wiley. 1998.    

Risorse Internet

Aggiornamenti alla pagina del corso

• A.A. 2010/2011
• A.A. 2011/2012
• A.A. 2012/2013
• A.A. 2013/2014
• A.A. 2014/2015
• A.A. 2015/2016
• A.A. 2016/2017
• A.A. 2017/2018
• A.A. 2018/2019
• A.A. 2019/2020