| | | |  corso | | | | |
Ottimizzazione combinatoria
| Codice: | AA032 | Crediti: | 6 | Semestre: | 2 | Sigla: | OC | |
| |
| Settore disciplinare: | MAT/09 - Ricerca Operativa |
Docente
Antonio Frangioni
Tel. 0502212789Obiettivi di apprendimento
Il corso si propone di fornire allo studente gli strumenti per progettare
e realizzare algoritmi di ottimizzazione combinatoria, nonché per
utilizzare in modo consapevole ed efficace gli strumenti software
attualmente disponibili.
Descrizione
Il corso presenta le tecniche fondamentali per la soluzione di problemi
"difficili" dell'Ottimizzazione Combinatoria, mostrando l'applicazione di
tali metodi alla soluzione di problemi di particolare rilevanza pratica o
teorica. In particolare, vengono presentati gli algoritmi di enumerazione
implicita (Branch & Bound) descrivendo nel dettaglio tutti i componenti
necessari per la loro realizzazione, ossia rilassamenti, euristiche,
tecniche poliedrali, tecniche di separazione e strategie di visita dell'albero
delle decisioni, e discutendo le problematiche relative all'integrazione di
tali componenti.
English Description
The course present the basic techniques for the solution of
"difficult" combinatorial optimization problems, showing how
these methods can be applied to the solution of relevant
problems. In particular, the course describes enumerative
(Branch & Bound) algorithms, detailing on thir fundamental
components (relaxations, heuristics, polyhedral techniques,
branching, visit of the decision tree) and discussing the issues
arising from the integration of these components.
Programma
- Introduzione
- Introduzione al corso
- Problemi e loro rappresentazione.
- Formulazioni
- Ottimalità ed algoritmi
- Dimostrazioni di ottimalità
- Valutazioni inferiori
- Valutazioni superiori e rilassamenti: rilassamento continuo,
rilassamento Lagrangiano, rilassamenti combinatori
- Algoritmi euristici
- Algoritmi "greedy"
- Algoritmi di ricerca locale
- Tecniche di rilassamento
- Rilassamento continuo
- Rilassamenti Lagrangiani e generazione di colonne
- Rilassamenti surrogati
- Algoritmi enumerativi
- Schema di algoritmo enumerativo
- Visita topologica e con informazione
- Regole di separazione
- Utilizzo di valutazioni post-ottimali
- Diseguaglianze valide (Branch & Cut)
| Ore lezione: | 0 | Ore esercitazione: | 0 | | | |
Bibliografia
Modalità di esame
Scritto e orale
