Network Design and Optimization Course

General Informations

Objectives and syllabus

See slides in lecture 1

Lecture topics and slides

• Lecture 01 (Sept 28th '11): Introduction to Network Design and Optimization (slides); introduction on basic routing problems ( slides ); Dijkstra's algorithm.
• Lecture 02 (Oct 4th '11): Routing (not so) basics (slides); Dijkstra's proof of correctness and computational complexity; Label Correcting algorithms, proof of correctness.
• Lecture 03 (Oct 11th '11): Review of shortest path algorithms.
• Lecture 04 (Oct 18th '11): More on routing ( slides ); Label Correcting algorithms computational complexity and improvements; All pairs shortest paths. Implementing Shortest Path Algorithms (data)
• Lecture 05 (Oct 20th '11): Basic design problems, minimum cost spanning trees (optimality conditions, Kruskal, Prim and Sollin algorithms, correctness and computational complexity) (slides).
• Lecture 06 (Oct 25th '11): Basic analysis problems, max flows (max flow - min cut duality, optimality conditions, basic algorithms) (slides).
• Lecture 07 (Nov 8th '11): Max flows algorithms (capacity scaling, shortest augmenting paths) (slides).
• Lecture 08 (Nov 9th '11): Modeling with max flows (network reliability, maximum matchings, network surveillance) (slides).
• Lecture 09 (Nov 10th '11): Handling capacities and costs at once: min cost flows (optimality conditions, capacity scaling, successive shortest path, primal-dual algorithms) (slides).
• Lecture 10 (Nov 16th '11) - lab session: implementing flow algorithms.
• Lecture 11 (Nov 17th '11): Multicommodity flows (optimality conditions, Lagrangean Relaxation, Column Generation) (slides).
• Lecture 12 (Nov 22th '11): Facility location (Basic models, Lagrangean Relaxation, Dual Ascent algorithms) (slides).
• Lecture 13 (Nov 24th '11) - lab session: implementing Lagrangean Relaxation and Column Generation for Multicommodity Flow Problems ( Lagrangean Relaxation source code , Column Generation source code ).
• Lecture 14 (Dec 1st '11): Facility location models in Network Design; Lagrangean Relaxation for Location problems.
• Lecture 15 (Dec 14th '11): Advanced design problems - Steiner Trees; metric Steiner Trees and Minimum Spanning Tree approximation algorithms ( slides ).
• Lecture 16 (Dec 15th '11): Advanced design problems - Steiner Forests; primal-dual approximation algorithms( slides ).
• Lecture 17 (Dec 20th '11): Robustness and protection in networks; global min cut algorithms and k-shortest path models ( slides ).
• Lecture 18 (Dec 21st '11): Protection in networks and integrated routing, design, dimensioning and protection models; local search and variable neighborhood search paradigms ( slides ).

Pointers to related material

• MIT OpenCourseWare: Network Optimization
• AMPL interpreters and solvers