Courses:

When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more.

15.082J/6.855J is an H-level graduate subject in the theory and practice of network flows and its extensions. Network flow problems form a subclass of linear programming problems with applications to transportation, logistics, manufacturing, computer science, project management, finance as well as a number of other domains. This subject will survey some of the applications of network flows and focus on key special cases of network flow problems including the following: the shortest path problem, the maximum flow problem, the minimum cost flow problem, and the multi-commodity flow problem. We will also consider other extensions of network flow problems.

The goals of the subject are the following:

• To present students with a knowledge of the state-of-the art in the theory and practice of solving network flow problems,
• To provide students with a rigorous analysis of network flow algorithms,
• To help each student develop his or her own intuition about algorithm development and algorithm analysis.

The required text is: Ahuja, Magnanti, and Orlin. Network Flows: Theory, Algorithms, and Applications. 1st ed. Upper Saddle River, NJ: Prentice Hall, February 18, 1993. ISBN: 013617549X. There will be weekly problem sets, each of which will consist of around 6 to 8 problems. In general, the TAs will grade a randomly selected subset of problems, but solutions will be provided for each of the problems. The subject will have one midterm and a final exam. The grading for the subject will be determined using the following weights, homework: 30%, midterm: 30%, final exam: 40%. The final exam will be comprehensive but will give more weight to the lectures subsequent to those covered on the midterm.

Homework sets may either be individual work, or may be carried out in groups of two persons. Many of the homework problems will involve proofs. We ask the following for proofs.

1. Students may discuss homework exercises with others outside of the group. However, no person should rely on a written solution of a homework exercise, even if one is available.
   
2. If homework sets are handed in as a group of two, then we suggest the following approach for writing a proof. Both members of the group should outline the proof as a team. Then one member of the group should write a draft, and the other member of the group critique it. This approach can help develop skills in writing proofs.
   
   Each homework set will be graded out of 3 points.
   • 3 points = "very good to excellent"
   • 2 points = "good"
   • 1 point = "fair"
   • 0 points = "poor"

Not all exercises will be graded, but we will provide a solution for each exercise.

Homework Sets will be due immediately prior to the following sessions:

• Session 4
• Session 5
• Session 7
• Session 9
• Session 11
• Session 14
• Session 16
• Session 18
• Session 19
• Session 21
• Session 23

Each homework set will be graded out of 3 points, and the lowest grade of the semester will be dropped.

We will be discussing a large number of algorithms in 15.082J/6.855J. It is often the case that algorithms become more clear, more intuitive, and easier to understand if they are "animated" on a computer. Collette R. Coullard, Jonathan H. Owen, and David Dilworth have developed a program called GIDEN that is consistent with the notation and pseudo-code used in the subject text book, and that animates a number of algorithms provided in the text.

You can access GIDEN through: GIDEN - A graphical environment for network optimization.

Although using GIDEN is not a requirement of 15.082J/6.855J, we do encourage you to check it out.

In addition, we have used Microsoft^® PowerPoint^® animations to illustrate a number of algorithms.

Microsoft^® and PowerPoint^® are either registered trademarks or trademarks of Microsoft Corporation in the United States and/or other countries.