Politecnico di Torino
Politecnico di Torino
   
Login  
en
Politecnico di Torino
Anno Accademico 2009/10
01KRWCY, 01KRWHR, 01KRWHT
Operations research and optimisation
Corso di L. Specialistica in Ingegneria Informatica - Torino
Corso di L. Specialistica in Ingegneria Telematica - Torino
Corso di L. Specialistica in Ingegneria Informatica (Computer Engineering) - Torino
Docente Qualifica Settore Lez Es Lab Tut Anni incarico
Tadei Roberto ORARIO RICEVIMENTO PO MAT/09 3.5 1.5 0 0 4
SSD CFU Attivita' formative Ambiti disciplinari
MAT/09 5 C - Affini o integrative Cultura scientifica, umanistica, giuridica, economica, socio-politica
Obiettivi dell'insegnamento
The main aim of the course is to give the students theoretical and operational tools for modelling and solving Operations Research and Optimization problems coming from telecommunications, in particular TLC networks.
Operations Research deals with the mathematical modelling of complex problems and related solution algorithms. Modelling the problem means to write it in terms of mathematical programming, i.e. identifying an objective function (which has to be minimized or maximized) and a set of constraints. Solving the problem means to find a solution which maximizes or minimizes the objective function without violating the constraints, and this is accomplished by using appropriate solution algorithms. Most recent solution algorithms will be discussed for each problem presented in the course.
The skills the students will get are those of problem solving for telematics problems.
Programma
1. Introduction to Linear Programming.
2. Graph problems: minimum spanning tree, mean flow cost, shortest path, max flow, maximum matching.
3. Computational complexity.
4. Exact methods for Combinatorial Optimization.
5. Heuristics for Combinatorial Optimization.
Programma (Prof. R. Tadei)
Obiettivi del corso
Il corso ha l'obiettivo di dotare gli studenti di strumenti teorici ed operativi per l'ottimizzazione di problemi di ingegneria nel discreto. Partendo da una serie di problemi reali e complessi, si sviluppa la teoria per la loro analisi, si costruiscono gli algoritmi relativi e si verifica la loro efficienza ed efficacia, sia dal punto di vista teorico sia da quello operativo.
Le competenze acquisite dagli studenti consistono nella capacitÓ di costruzione ed implementazione di algoritmi risolutivi di problemi discreti di ingegneria, quali progettazione di reti, localizzazione su reti, scheduling e routing, e nella conoscenza ed utilizzo dei pi¨ efficienti software di ottimizzazione oggi disponibili.


Programma
- Richiami di Programmazione Lineare.
- Problemi e complessitÓ computazionale.
- Metodi esatti di ottimizzazione combinatoria: Branch and Bound, Branch and Cut, Programmazione Dinamica.
- Metodi euristici di ottimizzazione combinatoria:
- euristiche costruttive: algoritmi greedy, algoritmi GRASP, Beam Search;
- metaeuristiche: Tabu Search, Simulated Annealing, Algoritmi genetici, Metodi ACO, VNS, RBS.
- Applicazioni su casi reali di Progettazione di Reti, Localizzazione su Reti, Scheduling e Routing.


Esercitazioni
Le esercitazioni consistono nello svolgimento in aula, da parte degli studenti e sotto la guida dei docenti, di esercizi e calcoli esemplificativi relativi agli argomenti trattati a lezione.


Laboratori e/o esercitazioni
The students will make practice both in modelling and solving engineering problems in the classroom and in running optimization software in the computer lab.
Bibliografia
R. Tadei, F. Della Croce, 'Elementi di Ricerca Operativa', Progetto Leonardo, Editrice Esculapio, Bologna, 2005.
R. Tadei, F. Della Croce, A Grosso, 'Elementi di Ottimizzazione', Progetto Leonardo, Editrice Esculapio, Bologna, 2005.
M. Ghirardi, A. Grosso, G. Perboli, 'Esercizi di Ricerca Operativa', Progetto Leonardo, Editrice Esculapio, Bologna, 2005.
D. J. Luenberger, "Introduction to Linear and Nonlinear Programming", Addison-Wesley, 1973.
M. Minoux, "Mathematical Programming: Theory and Algorithms", Wiley, 1986.
Testi e materiale didattico (Prof. R. Tadei)
R. Tadei, F. Della Croce, 'Elementi di Ricerca Operativa', Progetto Leonardo, Editrice Esculapio, Bologna, 2005.
R. Tadei, F. Della Croce, A. Grosso, 'Fondamenti di Ottimizzazione', Progetto Leonardo, Editrice Esculapio, Bologna, 2005.
M. Ghirardi, A. Grosso, G. Perboli, 'Esercizi di Ricerca Operativa', Progetto Leonardo, Editrice Esculapio, Bologna, 2009.
D. J. Luenberger, "Linear and Nonlinear Programming", Springer, 3rd ed., 2008.
M.S. Bazaraa, J.J. Jarvis. "Linear Programming and Network Flows", Wiley, 3rd ed., 2005.
R.K. Ahuja, T.L. Magnanti, J.B. Orlin, 'Network Flows', Prentice Hall, 1993.
G.L. Nemhauser, L.A. Wolsey, "Integer Programming", Wiley, 1998.


Verifica la disponibilita in biblioteca
ModalitÓ di verifica dell'apprendimento (Prof. R. Tadei)
Esame scritto


Orario delle lezioni
Statistiche superamento esami

Programma definitivo per l'A.A.2009/10
Indietro



© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
WCAG 2.0 (Level AA)
Contatti