Instructor

Dr. Sarah M. Ryan

3014 Black Engineering, 294-4347

smryan@iastate.edu

Office Hours

TR 1:30 - 3:00 p.m.

Time & Place

MWF 12:00 - 12:50 p.m., 1034 Black

Please note:  Contrary to ISU convention, we will begin at 12:00 promptly, not 12:10.

Text

Network Flows:  Theory, Algorithms and Applications,by Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, published by Prentice Hall, 1993

This book won the Institute for Operations Research and the Management Sciences (INFORMS) Lanchester Prize for the best contribution to OR/MS published in English in 1993.

Course Web Page

http://www.public.iastate.edu/~smryan/ie510/index.htm

Homework assignments and solutions and other material will be made available here as the semester progresses.  Check it often!

Description

Many optimization problems can be modeled in terms of flows through networks.  A network formulation can provide a clear visual representation of the problem and enable efficient solution methods.  In particular, many discrete and nonlinear problems can be solved very efficiently as network flows.

Homework exercises will be assigned every 1-2 weeks to be handed in and graded.  Students will complete semester projects chosen from their own interests or a suggested list.  There will be three exams.   

Tentative Topic List

The following sections in Ahuja, Magnanti and Orlin:

1.1-4  Introduction

2.1-5 Paths, Trees and Cycles

3.1-6 Algorithm Design and Analysis

4.1-5  Shortest Paths:  Label-Setting Algorithms

5.1-6  Shortest Paths:  Label-Correcting Algorithms

Chapters 4 and 5 will be supplemented with instructor’s notes on dynamic programming formulation, application and methods.

6.1-6  Maximum Flows:  Basic Ideas

7.1-2,6-7  Maximum Flows:  Polynomial Algorithms

9.1-7     Minimum Cost Flows:  Basic Algorithms  

11.1-5, 12 Minimum Cost Flows:  Network Simplex Algorithms

12.1-6   Assignments and Matchings

13.1-5    Minimum Spanning Trees

19.7-9  Additional Applications  

Grading

20%

20%

15%

20%

25%

Homework

Project

Progress Reports: 5%

Written Report: 10%

Presentation: 5%

Exam 1 (in class)

Exam 2 (in class)

Exam 3 (Friday, Dec. 17, 9:45-11:45 a.m.)

Academic Integrity

Discussion of homework exercises and student projects is encouraged. No late homework will be accepted since solutions will be discussed in class and/or posted on the course web page.  The lowest homework grade will be dropped.  Exams will be strictly individual efforts.  Cheating on an exam will result in a failing grade for the course.