Network Optimization
Graduate network flows: shortest paths, maximum flow, minimum cost flow, multicommodity flows and relaxation, with notes, problems and a project.
Transportation, logistics, manufacturing and finance all produce problems that can be modeled as flows through a network. This graduate subject teaches the theory and practice of solving them, with rigorous analysis of the algorithms involved. Beyond the classic special cases, it extends to NP-completeness and relaxation methods, and asks students to develop their own intuition for designing and analyzing algorithms.
What You Will Achieve
- Solve shortest path, maximum flow and minimum cost flow problems
- Analyze the running time of network flow algorithms
- Model applied problems as network flows
- Research and present a project on a network topic
Program Overview
Search and Shortest Paths
Foundations and the first family of algorithms.
- Computational complexity and data structures
- Graph search algorithms
- Label setting and label correcting algorithms
- The radix heap algorithm
Maximum and Minimum Cost Flow
The central problems and their algorithms.
- Preflow push algorithms
- Combinatorial applications of maximum flows
- Polynomial time algorithms
- The network simplex algorithm
Lagrangian Relaxation and Multicommodity Flows
Harder problems and ways to approach them.
- NP-completeness
- Lagrangian relaxation
- Multicommodity flows
Course Completion
Job Outlook
These skills apply to operations research, logistics, transportation planning and algorithm development.
Good for: Graduate students in operations research or computer science who want a rigorous treatment of network flow algorithms.
Keep in mind: Problem sets rely on the Ahuja, Magnanti and Orlin textbook, so you need a copy. Only practice problems for one midterm are published, and no solutions or videos are listed.
Bottom line: A thorough course on network flows, best followed with the textbook in hand.
Frequently Asked Questions
What textbook is used?
Network Flows: Theory, Algorithms, and Applications by Ahuja, Magnanti and Orlin, published by Prentice Hall in 1993. The problem sets assign readings and problems directly from it.
What kind of project is suggested?
Teams of two or three write a paper of 10 to 15 pages and give a 20-minute presentation. Suggested topics include visualizing networks, a new approximation algorithm for maximum flows, and social networks.
Is exam practice included?
Partly. Review and practice problems for the second midterm are published. The materials do not list the exams themselves, or solutions to the five problem sets.



There are no reviews yet.