- Docente: Paolo Toth
- Crediti formativi: 6
- SSD: MAT/09
- Lingua di insegnamento: Italiano
- Moduli: Paolo Toth (Modulo 1) Paolo Toth (Modulo 2)
- Modalità didattica: Convenzionale - Lezioni in presenza (Modulo 1) Convenzionale - Lezioni in presenza (Modulo 2)
- Campus: Bologna
- Corso: Laurea Magistrale in Ingegneria informatica (cod. 0937)
Conoscenze e abilità da conseguire
Conoscenza approfondita dei modelli matematici per problemi di ottimizzazione combinatoria. Algoritmi di tipo enumerativo per la soluzione ottima dei problemi: programmazione dinamica, branch-and-bound, branch-and-cut, branch-and-price. Soluzione di problemi di grande dimensione. Valutazione sperimentale degli algoritmi.
Contenuti
Classificazione dei Problemi di Ottimizzazione. Modelli Matematici dei Problemi di Ottimizzazione Combinatoria (e loro Complessità Computazionale). Utilizzazione di “pacchetti” software (CPLEX) per la soluzione di modelli di Programmazione Lineare Continua e Mista. Algoritmi Esatti per Problemi NP-Difficili: “Branch-and-Bound”: Rilassamenti, Schemi di “branching”, Criteri di Dominanza, Problemi di Grandi Dimensioni, Knapsack Problem (KP), Subset Sum Problem, Asymmetric Traveling Salesman Problem (ATSP); “Branch-and-Cut”: Procedure di “Separazione”, ATSP; “Branch-and-Price”: Procedure di “Pricing”, Generazione di Colonne, Bin Packing Problem, Vertex Coloring Problem.
Testi/Bibliografia
• S. Martello, P. Toth, Knapsack Problems: Algortihms and
Computer Implementations, J. Wiley, 1990.
• R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows:
Theory, Algorithms, and Applications, Prentice Hall, 1993.
• G. Gutin, A. Punnen (editors), The Traveling Salesman
Problem and Its Variations, Kluwer, 2002.
• P. Toth, D. Vigo (editors), The Vehicle Routing
Problem, SIAM Monographs on Discrete Mathematics and Applications,
2002.
• C. Barnhart, G. Laporte (editors), Transportation,
Handbooks in Operations Research and Management Science, North
Holland, 2007.
• Wiley Encyclopedia in Operations Research and Management
Science, Wiley, 2011.
Metodi didattici
Lezioni in Aula; Esercitazioni in Aula; Esercitazioni in Laboratorio.
Modalità di verifica e valutazione dell'apprendimento
Prove scritte sulla definizione di modelli matematici, sullo studio della complessita` computazionale, sulla definizione e soluzione di problemi rilassati, sulla progettazione di algoritmi esatti, sulla implementazione di modelli matematici in CPLEX.
Strumenti a supporto della didattica
Copie dei trasparenti,proiettati durante le lezioni e le
esercitazioni, disponibili sul sito www.UniversiBo.it
Orario di ricevimento
Consulta il sito web di Paolo Toth