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:

• 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):

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.