1) Capacità di formulare problemi di ottimizzazione combinatoria.
2) Conoscenza di algoritmi per problemi di ottimizzazione su rete e di ottimizzazione combinatoria.
3) Capacità di applicare e adattare, a specifici contesti applicativi, algoritmi standard di ottimizzazione combinatoria.
Prerequisiti
Nozioni base di ricerca operativa e algebra lineare.
Metodi Didattici
Didattica frontale
Altre Informazioni
Il corso utilizza in parte materiali e risorse online
Modalità di verifica apprendimento
Esame orale attraverso il quale si verifica mediante quesiti e domande teoriche:
- la capacità di formulare problemi di ottimizzazione combinatoria e su rete;
- la capacità di descrivere e utilizzare algoritmi di ottimizzazione combinatoria;
- la capacità di adattare modelli e algoritmi di ottimizzazione combinatoria per la soluzione di problemi complessi previa identificazione della loro struttura.
Programma del corso
Ottimizzazione Combinatoria.
Parte 1.
Modellizzazione di problemi con variabili binarie e intere
• Problemi di flusso su grafo: una breve rassegna di problemi di facile risoluzione.
• Problemi di assegnamento.
• Problemi di covering, partitioning, packing.
• Alberi di copertura di costo minimo.
• Problemi di Vehicle Routing.
• Problemi di flusso multicommodity.
• Problemi di network design.
Parte 2.
Algoritmi per risolvere problemi di Ottimizzazione Combinatoria.
• Rilassamenti lineari e lagrangiani.
• Teoria poliedrale: generazione di disuguaglianze valide, facce e faccette.
• Algoritmo dei piani di taglio (generazione di righe).
• Algoritmo di generazione di colonne: il problema master e il sottoproblema di pricing.
• Branc&Cut.
• Algoritmi di decomposizione.
Parte 3.
Incertezza dei dati e robustezza.
• Meccanismi di re-establishment nel network design.
• Modelli alternativi: (i) protection e (ii) restoration. Ripristino di link vs path. Gestione delle risorse: dedicata vs condivisa.
• Ottimizzazione robusta