IOE 612
Network Flows

<HR>

Instructor: Professor Katta G. Murty, 2773 IOE Bldg., 763-3513, katta_murty@umich.edu

Prerequisites: A course in linear programming (IOE 510 or equivalent)

Text: K G Murty, Network Programming, Prentice Hall, 1992.

Transparencies: The course will be taught using overhead transparencies. Registered students will have access to these transparencies at the website: http://www.engin.umich.edu/class/ioe612.

Course Content:

  1. Network optimization and routing models, background, history, and applications.
  2. Network definitions, fundamentals, and formulations.
  3. Maximum flows in pure networks.
  4. Shortest route algorithms.
  5. Primal-Dual algorithms for assignment and transportation problems.
  6. Min cost flow algorithms.
  7. Critical path methods in project networks.
  8. Spanning trees
  9. Matchings and their routing applications.

Workload:

Lecture Notes (Transparencies):

Notes 0....21 pages: Flow & routing models (612slides0.pdf)
Notes 1....9 pages: History & some applications (612slides1.pdf)
Notes 2....57 pages: Notation (612slides2.pdf)
Notes 3....44 pages: Single commodity max flows (612slides3.pdf)
Notes 4....36 pages: Primal-dual algorithms (612slides4.pdf)
Notes 5....41 pages: Shortest chains (612slides5.pdf)
Notes 6....51 pages: Min cost flows (612slides6.pdf)
Notes 7....16 pages: Generalized network flows (612slides7.pdf)
Notes 8....18 pages: Project management applications (612slides8.pdf)
Notes 9....6 pages: Mic cost spanning trees (612slides9.pdf)
Notes 10....2 pages: Multicommodity flows (612slides10.pdf)
Latest Homework (612hw.pdf)
 
The figures are missing from these transparency copies
you have to draw them by hand in your copy in class.
They will be displayed on the screen in the class.
If you are printing these notes, please print each set of
notes only when the class is getting ready to discuss it.
Please try to minimize the amount of paper you use for
this course.

<HR>

HOMEWORK 1

Construct a network model for the following Meeting scheduling problem: At an international conference, 19 seminars numbered 0 to 18 are planned. The attendees have been polled and asked to indicate which seminars they plan to attend. Based on the responses, a pair of seminars is classified as a conflicting pair if some attendees want to visit both of them. The set of all conflicting pairs is:

{(0, 8), (0, 12), (1, 6), (2, 10), (2, 12), (3, 12), (5, 6), (7, 9), (13, 17), (0, 3), (0, 13), (1, 4), (2, 13), (3, 14), (4, 15), (5, 15), (8, 11), (14, 17), (0, 5), (1, 10), (1, 12), (2, 4), (3, 8), (4, 8), (5, 16), (9, 18), (16, 18), (0, 4), (1, 7), (1, 5), (2, 9), (3, 11), (4, 17), (6, 7), (10, 18), (0, 9), (1, 11), (2, 6), (2, 7), (3, 16), (5, 10), (6, 15), (11, 14)}

Each seminar takes exactly one hour. Two seminars can be held in parallel in the same time slot iff they do not form a conflicting pair. Subject to this constraint it is required to arrange the seminars using as many parallel sessions as possible at any point of time, so as to keep the conference as short as possible.

<HR>