Scheda programma d'esame
NETWORK OPTIMIZATION
(NETWORK OPTIMIZATION METHODS)
MARIA GRAZIA SCUTELLA'
Anno accademico2017/18
CdSINFORMATICA E NETWORKING
Codice533AA
CFU6
PeriodoSecondo semestre
LinguaItaliano

ModuliSettoreTipoOreDocente/i
METODI DI OTTIMIZZAZIONE DELLE RETIMAT/09LEZIONI48
MARIA GRAZIA SCUTELLA' unimap
Programma non disponibile nella lingua selezionata
Learning outcomes
Knowledge

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.

Assessment criteria of knowledge

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
Teaching methods

Delivery: face to face

Learning activities:

  • attending lectures
  • participation in discussions
  • individual study

Attendance: Advised

Teaching methods:

  • Lectures
Syllabus

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.

Bibliography

- 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.

Ultimo aggiornamento 02/08/2017 09:38