Network Optimization, 9.0 credits

Entry requirements

At least one optimization course. Basic programming. Linear programming is recommended.

Learning outcomes

After completing the course, the student should be able to:

• formulate optimization problems on networks,
• analyze structural properties of network optimization problems,
• explain and apply classical algorithms for network optimization problems,
• evaluate the computational complexity and practical performance of network optimization algorithms,
• implement and test selected algorithms computationally,
• model and solve realistic large-scale applications using network optimization techniques.

Contents

The course gives a broad orientation of the foundations of network optimization, including modelling, theory, algorithms, and applications for optimization problems on graphs and networks.

The course covers network models, shortest path problems, maximum flow and minimum cut problems, minimum cost flow problems, matching and assignment problems, multicommodity flow models, decomposition methods for large-scale optimization problems, and computational complexity and algorithmic analysis of network optimization methods.

Educational methods

Seminars where the participants present the course topics and solutions to the assigned exercises.

Examination

The course examination consists of:

• Active participation in course sessions.
• Presentation of selected topics from the course literature.
• Submission and presentation of assigned exercises.
• Implementation of a programming assignment on a network optimization problem.

Grading

Course literature

Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.