(NETWORK OPTIMIZATION METHODS)
CdSINFORMATICA E NETWORKING
Codice533AA
CFU6
PeriodoSecondo semestre
LinguaInglese
| Moduli | Settore/i | Tipo | Ore | Docente/i | |
| METODI DI OTTIMIZZAZIONE DELLE RETI | MAT/09 | LEZIONI | 48 |
|
The student who successfully completes the course will have the ability to formulate and solve both basic and NP-Hard problems arising in communication networks. Specifically, he/she will obtain a solid background on basic network flow problems, and based on such a knowledge he/she will get the competence to mathematically formulate and solve relevant hard optimization problems, with emphasis on design and operational problems in communication networks. In particular, the student will be aware of the basic properties characterizing network optimization problems, and will be able to exploit them to design efficient algorithmic approaches to solve the studied problems.
During the oral exam the student must be able to demonstrate his/her knowledge of the course material, and he/she must be able to discuss the main course contents using the appropriate terminology.
Methods:
- Final oral exam
Delivery: face to face
Learning activities:
- attending lectures
- participation in discussions
- individual study
Attendance: Advised
Teaching methods:
- Lectures
The first lessons will be devoted to basic network flow problems such as the minimum cost flow problem and multicommodity flow problems. Then, the main part of the course will be about optimization methods, especially for network design: mathematical formulations (optimality, relaxations and bounds); Branch and Bound algorithms; valid inequalities; cutting plane algorithms; Lagrangean Duality and column generation techniques. Finally, the last group of lessons will be dedicated to advanced models and methods for network design, such as location and topological design, shortest-path routing, restoration and protection (resiliency). Further details can be found at http://didawiki.cli.di.unipi.it/doku.php/magistraleinformaticanetworking/mor/start.
- R.K. Ahuja, T.L. Magnanti, J.B. Orlin. Network flows. Theory, algorithms and applications, Prentice Hall, New Jersey, 1993
- L.A. Wolsey. Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization, 1998
- M. Pioro, D. Medhi. Routing, Flow and Capacity Design in Communication and Computer Networks, Elsevier, 2004.
Teacher notes are also available at http://didawiki.cli.di.unipi.it/doku.php/magistraleinformaticanetworking/mor/start.