Network Flows

**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:**

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

**Workload:**

- There will be homework assignments every week which will be graded. Homework 1 is given below. Future homeworks can be found here.
- Midterm in the class on 5 Nov 03, final on 12 Dec. 03, 4 to 6 PM.
- The weights of the various inputs in the final grade will be: Homeworks (20%), Midterm (30%), Final (50%).

**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. |

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.