Ottimizzazione Industriale & Logistica

Ottimizzazione Combinatoria II

Orario

Mercoledì dalle ore 9.30 alle ore 11.30 AULA 1.6
Giovedì dalle ore 09.30 alle ore 11.30 AULA C.1.15
Venerdì dalle ore 11.30 alle ore 13.30 AULA 0.6

Top

Lezioni

I Settimana
Mercoledì 04 Aprile 2007
Introduzione al corso. Esempi di problemi di programmazione lineare intera: problema dell'assegnamento e problema di set-covering.
II Settimana
Mercoledì 11 aprile 2007
Formulazione lineare di un problema di programmazione lineare intera. Indipendenza lineare e affine, involucro convesso. Gerarchia di formulazioni.
Giovedì 12 aprile 2007
Condizioni di ottimalità per un problema di programmazione lineare intera. Definizione di rilassamento. Formulazioni e rilassamenti del problema del massimo insieme stabile.
Venerdì 13 aprile 2007
Disequazioni valide per un poliedro. Definizione di dimensione, vertice, faccia e faccia massimale di un poliedro. Dominanza tra disequazioni. Esempi di disequazioni valide per poliedri noti: problema di Knapsack.
III Settimana
Giovedì 19 aprile 2007
Esempi di disequazioni valide per un poliedro: problema matching di peso massimo, Integer rounding. Procedura di Chvátal-Gomory per costruire disequazioni valide. Chiusura i-esima di Chvátal di una formulazione. Convergenza del metodo di Chvátal-Gomory.
Venerdì 20 aprile 2007
Rango di Chvátal di una disequazione. Esempio: massimo insieme stabile. Algoritmo di piani di taglio.
IV Settimana
Giovedì 26 aprile 2007
Algoritmo di piani di taglio di Gomory. Esempi.
Venerdì 27 aprile 2007
Metodo del simplesso duale. Vantaggi e svantaggi del metodo dei piani di taglio di Gomory.
V Settimana
Mercoledì 2 maggio 2007
Approccio poliedrale del Metodo di piano di taglio. Problema del cammino minimo. Problema del commesso viaggiatore.
Giovedì 3 maggio 2007
Approccio poliedrale del Metodo del piano di taglio per il problema del massimo insieme stabile. Algoritmo di separazione della famiglia delle disequazioni cicli dispari.
Venerdì 4 maggio 2007
Rilassamento lagrangiano. Duale lagrangiano. Applicazione al problema di set-covering. Condizioni di ottimalità per il problema lagrangiano.
VI Settimana
Mercoledì 9 maggio 2007
Qualità del bound lagrangiano. Metodo del subgradiente. Applicazione al problema di set-covering.

Top