Dettagli sull'Insegnamento per l'A.A. 2010/2011
Nome:
Ottimizzazione Combinatoria II / Combinatorial Optimization II
Informazioni
Lingua:
Italiano
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.
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: 08 aprile 2011, 09:34