Skip to main content

Before choosing course

Network optimization theory provides the methods of optimal decision making over networks. It has pervasive applications in engineering, such as in Communication Networks allocation and control, Signal Processing, Big Data analysis, Smart Grids, Intelligent Transportation Systems, and Financial Market, to mention a few. In these application domains, typical problems are those of routing, auctions, resources assignment, minimum cost flow, traveling salesman, generalized assignment, spanning tree, and matching.

This course provides an overview on network optimization fundamentals and engineering applications with focus on linear, nonlinear, and discrete problems. The interplay between discrete and continuous problem structures will be highlighted. Discrete network optimization problems will be discussed in the detail. In the case of continuous network optimization, duality and iterative cost improvement will be studied and applied in most common linear cost problems, such as minimum cost flow and transshipment problems. Main solution methods, including branch-and-bound, Lagrangian relaxation, Dantzig-Wolf decomposition, heuristics, and local search methods will be studied.

The course will present in the detail some selected applications to engineering problems of societal impact, such as Optimal Access Point Assignment in wireless networks, Optimal Power Flow in smart grids, multi-agent scheduling in Intelligent Transport Systems, and Privacy Preserving optimization.

Course offering missing for current semester as well as for previous and coming semesters
* Retrieved from Course syllabus FEL3350 (Spring 2014–)

Content and learning outcomes

Course contents

1. Introduction to Network Optimization (L1)

- based on chapter 1 of the course text

- establish terminology and basic notations

- discuss examples of key network models

- provide basics of linear network optimization

2. Shortest path problems (L2)

- based on chapter 2 of the course text

- highlight example application domains

- discuss major methods to address the problem

- discuss the performance of algorithms

3. The Max-Flow problem (L3)

- based on chapter 3 of the course text

- highlight example application domains

- discuss major methods to address the problem

4. The Min-Cost Flow problem (L4)

- based on chapter 4 of the course text

- discuss equivalent variants

- develop duality results in connection with the problem

5.Auction algorithm for Min-Cost Flow (L5)

- based on chapter 7 of the course text

- discuss algorithms design steps

- discuss variants of auction algorithm

6. Network flow arguments for bounding mixing times of Markov chains (L6)

- introduce the concept of mixing time of Markov chains

- conductance bounds and relation to eigenvalues

- multi-commodity flow and the method of canonical paths

7. Accelerated dual descent for network flow optimization (L7)

- review of Newton's method

- approximate Newton method based on network structure

Intended learning outcomes

After finishing the course, the attendant will be able to

- describe and explain the basics of linear, non linear, and discrete optimization

- demonstrate and explain the essential properties of network optimization theory

- analyze in depth key network optimization problems

- give detailed descriptions of applications of network optimization to practical engineering problems

- develop a research project and contribute to research frontiers in the area

Course Disposition

7 lectures (2h per lecture), 5 exercise sessions (1h per session), 5 homework sheets, 1 take home exam and a research project.

Literature and preparations

Specific prerequisites

No information inserted

Recommended prerequisites

No information inserted

Equipment

No information inserted

Literature

D. P. Bertsekas, Network Optimization Continuous and Discrete Models, Athena Scientific, Belmont, Mass., USA, 1998.

Examination and completion

If the course is discontinued, students may request to be examined during the following two academic years.

Grading scale

P, F

Examination

    Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

    The examiner may apply another examination format when re-examining individual students.

    Other requirements for final grade

    To pass the course, a passing grade must be achieved for each and every of the following category:

    - Attendance: a passing grade is achieved by attending at least two out of seven lectures;

    - Homework: a passing grade is achieved by successfully completing two out of five homeworks;

    - Course project: a passing grade is achieved by successfully completing the project;

    - Final exam: a passing grade is achieved by successfully

    Opportunity to complete the requirements via supplementary examination

    No information inserted

    Opportunity to raise an approved grade via renewed examination

    No information inserted

    Examiner

    Profile picture Carlo Fischione

    Ethical approach

    • All members of a group are responsible for the group's work.
    • In any assessment, every student shall honestly disclose any help received and sources used.
    • In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

    Further information

    Course web

    No information inserted

    Offered by

    EECS/Decision and Control Systems

    Main field of study

    No information inserted

    Education cycle

    Third cycle

    Add-on studies

    No information inserted

    Postgraduate course

    Postgraduate courses at EECS/Decision and Control Systems