Network Optimization

• Analyze and evaluate the suitability of linear/integer programming techniques for formulating and solving network optimization problems.
• Create and develop primal-dual algorithms to solve network optimization problems arising in areas such as traffic and transportation optimization, and production planning.
• Describe and use the central algorithms for the classical network problems: minimum spanning tree, shortest path, project planning, maximum flow, minimum cost flow and multicommodity flow
• Solve network optimization problems using specialized algorithms frequently based on techniques from linear/integer programming, primal-dual algorithms, and decomposition.
• Evaluate and select appropriate graphs and networks as modeling tools for complex problems.
• Analyze and evaluate the worst-case time complexity of algorithms used for network optimization problems.
• Evaluate and interpret the central theorems within network optimization, including running time and correctness of the presented algorithms.
• Develop and implement simple data structures for graph algorithms.
• Independently formulate and solve a larger network optimization problem using appropriate algorithms and techniques.
• Communicate the findings and results of a given network optimization problem in a written report.
• To be able to use graphs and networks as modelling language

Algorithms for networks: review of relevant graph theory. Algorithms for shortest paths, maximal flows in capacitated networks, and minimal cost flows and multicommodity flow. Application of graphs and networks to model complex problems.

Lectures, exercises, project work