Progetto di Reti A. A. 2011-2012

    Prof. Fabrizio Rossi

Orario

Materiale didattico

Orario di Ricevimento

Calendario prove parziali e appelli

Programma

Testi di Riferimento

Temi di Esame 2011-2012

Orario

Martedì

11.30 - 13.15 Aula 1.6 (Modulo di Progetto e Ottimizzazione di Reti)
14.15 - 16.00 Aula 1.7 (Modulo di Ottimizzazione Combinatoria 2)

Giovedì

11.30 - 13.15 Aula 1.6 (Modulo di Progetto e Ottimizzazione di Reti)
14.15 - 16.00 Aula 1.6 (Modulo di Ottimizzazione Combinatoria 2)

Top

Materiale didattico

Progetto e Ottimizzazione di Reti

Slide delle lezioni

• Lezioni Parte 1
• Lezioni Parte 1 (formato .pdf)


• Lezioni Parte 2
• Lezioni Parte 2 (formato .pdf)

Testo degli esercizi svolti a lezione

• Esercizi

Ottimizzazione Combinatoria 2

Alcuni esercizi

• Esercizi (1)
• Esercizi (2)

Top

Orario di Ricevimento

Nel periodo del corso il ricevimento si effettua il martedì e il giovedì dalle 16.00 alle 18.00.
È possibile concordare altri orari su richiesta.

Top

Prove di esame

Risultati Prima Prova parziale Modulo di Progetto e Ottimizzazione di Reti

Risultati Seconda Prova parziale Modulo di Progetto e Ottimizzazione di Reti

Risultati Prova Totale del 25 giugno (Modulo di Progetto e Ottimizzazione di Reti)

    Top

Programma

Modulo di Progetto e Ottimizzazione di Reti
Il programma d'esame è descritto nella slide numero 3 di Lezioni Parte 1

Modulo di Ottimizzazione Combinatoria 2

Prima parte: metodi di Programmazione Lineare Intera

1. Formulazioni
• Formulazioni di problemi di Ottimizzazione Combinatoria
• Formulazioni di Programmazione Lineare Intera, Intera Mista, Binaria
• Gerarchia delle formulazioni: formulazioni ideali
2. Ottimalità, Rilassamenti e Buond
• Ottimalità e rilassamenti
• Rilassamenti lineari
• Bound primali e duali
3. Branch-and-bound
• Schema di enumerazione
• Branch-and-bound per i problemi di Programmazione Lineare Intera e Binaria
• Parametri di controllo dell'algoritmo di branch-and-bound
• Preprocessamento dei problemi di Programmazione Lineare
4. Tool software
• GLPK (GNU Linear Programming Kit)
• ZIMPL
5. Algoritmi ``Piano di taglio''
• Disuguaglianze conseguenza di implicazioni logiche
• Disuguaglianze valide
• Tagli di Gomory
• Algoritmo del piano di taglio
6. Branch-and-cut
• Disuguaglianze ``cover'' per problemi di knapsack: separazione
• Formulazioni con numero esponenziale di vincoli: minimo albero ricoprente
• Separazione dei vincoli ``subtour elimination''
• Il problema del commesso viaggiatore (TSP)

Riferimenti

Wolsey, Integer Programming, Wiley 1998
Capitoli 1,2,7,8,9
Materiale integrativo

• Lezione sul TSP
• Slide

    Top

Testi di riferimento

• Cook, Cunningham, Pulleyblank, Schrijver, Combinatorial Optimization, Wiley, 1998
• Ahuja, Magnanti, Orlin, Network Flows, Prentice Hall, 1993
• Wolsey, Integer Programming, Wiley 1998

Top

Temi di Esame 2011-2012

Top