Ottimizzazione Combinatoria 2 A.A. 2007/2008 Programma del corso
Prima parte: Formulazioni di Problemi di Ottimizzazione Combinatoria Problemi di Ottimizzazione Combinatoria: richiami e definizioni [1], [2].
Problemi di Programmazione Lineare Intera e di Programmazione Lineare
{0, 1}: problema di assegnamento, problema di set covering, problema di knapsack, problema del commesso viaggiatore (TSP) [1], [2].
Formulazioni di Programmazione Lineare Intera Mista: modellizzazione di costi fissi, problema di localizzazione degli impianti [1].
Formulazione di vincoli logici (and, or) e di alternative discrete (disgiunzioni): formulazione di problemi di scheduling a macchina singola [1].
Ottimalità, rilassamenti e bound [2], [3]
Richiami di geometria della PL: spazi lineari e affini;
poliedri e rappresentazioni, dimensione di un poliedro;
disequazioni valide, facce, vertici, facce massimali;
gerarchia di formulazioni e formulazioni ideali [2], [4], [5].
Seconda parte: Algoritmo di branch-and-bound per la PLI Enumerazione implicita e schema di base dell’algoritmo [2] [6]
Regole di selezione del sottoproblema (depth-first, best-bound) [6]
Regole di selezione della variabile di branching e della direzione di branching [6]
Fixing delle variabili per costo ridotto [7]
Preprocessamento dei problemi di Programmazione Lineare {0,1} [6][7]
Terza parte: Piani di taglio
Tagli di Chvatal-Gomory: definizione e separazione [4]
Disequazioni cover: definizione e separazione [2] [8]
Lifting di disequazioni cover [8]
Algoritmo del piano di taglio [7][8]
Algoritmo di branch-and-cut [7][8]
Quarta parte: Rilassamento Lagrangiano Rilassamento Lagrangiano [7]
Qualità del rilassamento Lagrangiano [7]
Euristiche lagrangiane [7]
Riferimenti
[1] L.A. Wolsey, Integer Programming, Capitolo 1 [2] Slide del corso di Ottimizzazione Combinatoria
[3] L.A. Wolsey, Integer Programming, capitolo 2, paragrafi 2.1, 2.2 [4] Slide del corso di Ottimizzazione Combinatoria 2, prof. Smriglio [5] L.A. Wolsey, Integer Programming, Capitolo 9, paragrafi 9.1, 9.2 [6] L.A.Wolsey, Integer Programming, Capitolo 7
[7] Materiale integrativo
[8] L.A. Wolsey, Integer Programming, Capitolo 9, paragrafo 9.3, 9.4, 9.5 [9] L.A. Wolsey, Integer Programming, Capitolo 10
