Course Unit Profile

<--- Back to Course Diagram

Basic Information

Course Unit Title: NETWORK OPTIMIZATION METHODS

Course Unit Code: 533AA

Level of course unit

Second Cycle (Laurea magistrale) Degree Programme in Computer Science and Networking

Year of study

Second year

Semester when the course is delivered

Second semester

Number of ECTS credits allocated: 6

Name of Lecturer(s):

Prof.: Maria grazia Scutella'
Email: maria.grazia.scutella@unipi.it

Language of instruction

English

General Information

Learning outcomes

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.







Course contents

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.


Specific Information

Prerequisites, co-requisites, as a prerequisite for further study

Prerequisites

For this course the prerequisite/s is/are

Co-requisites

None.

Prerequisite for

None.

Mode of delivery

Delivery

face to face

Attendance

Advised

Teaching methods

Learning activities

Recommended or required reading

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

Assessment methods and criteria

Assessment methods

Assessment criteria

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.

Work placement

No

<--- Back to Course Diagram