Network Optimization

View Course Materials

Buying via our links supports this free directory · Affiliate disclosure.
Course facts
  • Payment: Free, no certificate
  • Credits: Non Credit
  • Learning style: Self-paced, start anytime
  • Resources: Lecture Notes; Problem Sets; Projects
  • Before you start: 6.251J/15.081J Introduction to Mathematical Programming or a course on data structures.
MIT OpenCourseWare details
  • As taught in: Fall 2010
  • Department: Sloan School of Management, Electrical Engineering and Computer Science, Engineering Systems Division
Created byMIT
Available onMIT OpenCourseWareMIT OpenCourseWare

Course Details
Learning Style

Start Anytime

Level

All Levels

Study Mode

100% Online

Outcomes
Academic Credits

Non Credit

Price & Terms
Pricing Model

Free Content (No Certificate)

Technical
Content Medium

Text Based

Specification
Access

Free Access

Academic Level

Graduate

SKU: network-optimization Category: Brand:

Graduate network flows: shortest paths, maximum flow, minimum cost flow, multicommodity flows and relaxation, with notes, problems and a project.

At a glance
LevelAll Levels
AccessFree access
FormatText Based
As taught inFall 2010
DepartmentSloan School of Management, Electrical Engineering and Computer Science, Engineering Systems Division
Add your review
Add to wishlistAdded to wishlistRemoved from wishlist 0
Add to compare

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.


Our take

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.

User Reviews

0.0 out of 5
★★★★★
0
★★★★★
0
★★★★★
0
★★★★★
0
★★★★★
0

No reviews yet. Be the first to review this course.

There are no reviews yet.

Write your review

Reviews can only be posted by registered learners. Log in, then you will return here to post.

×

    Report this page
    LiveTalent
    Logo
    Compare items
    • Total (0)
    Compare
    0