Systems
Engineering and Operations Research Department
Mondays,
Professor Karla L. Hoffman
Office: SciTech Building II, Room 123
Phone: (703)993-1679(direct) or 993-1670 (office)
Homepage: http://iris.gmu.edu/~khoffman/hoffman.html
Homepage for Course: http://iris.gmu.edu/~khoffman/or643_f06/or643_f06.html
All lecture notes, homework assignments, the posting of grades, etc will appear at: webct41.gmu.edu.
To access these lecture notes, you will need to have registered for the course and have an active email account at GMU. You will log onto the webct site by using your email address name and password.
Office hours: Mondays:
I am usually on Mondays and Wednesdays from
Text: Network Flows: Theory, Algorithms and Applications, by Ravindra K. Ahuja, Thomas L. Magnanti and James B. Orlin, published by Prentice Hall 1993.
Course Description: This course is about modeling, solving and understanding network flow problems. Such problems arise naturally in many disciplines such as telecommunications, transportation, electronic circuitry, wataer distribution. In addition, they can be used to solve many problems where the connection with networks is not immediately obvious. A network formulation can provide a clear visual representation of the problem enable efficient solutions methods. There are three general topic areas covered in this course: Modeling and understanding network application areas, algorithmic development of network algorithms including proofs of correctness of such algorithms and computational measurements of �goodness� for such algorithms. The study of network flows involves concepts from optimization, complexity theory, and data structures.
Software: You will be expected to use a software package called GIDEN. You can download this software from: http://giden.northwestern.edu/
Main Goals:
Enable one to formulate optimization problems as networks and graphs (i.e. as collections of nodes and arcs with information about any restrictions on flow, any side constraints, and other data-related issues and be able to specify an appropriate objective function)
Learn the terminology of graph theory and cover the fundamental algorithmic ideas for solving the main categories of network flow problems.
Identify what makes an algorithm computationally efficient
Understand simple algorithms for searching, topological ordering and decomposing flows on networks
Navigate data structures used to represent network algorithms on computers
Be able to solve efficiently shortest path, maximum flow, minimum cost flow, minimal spanning tree, assignment and matching problems.
Be able to identify when alternative algorithms for each problem is likely to be most efficient.
Homework and Grading:
Homework problems will be assigned each week. Some or all of the assignments will be collected and graded.
There will be one in-class midterm exam and the final will also be in class. All exams will be open book and open notes.
Grades will be computed as follows:
l 30% homework
l 30% midterm
l 30% final (20/15 take home and in-class)
l 10% Class participation:
You are expected to come to class each week having read the materials assigned.
Course Outline:
The course will include all or part of the following chapters from the Network Flow text, covered in the indicated sequence. The exact scheduling will depend upon the interests of the class, which will determine the amount of time that will be devoted to each topic.
WEEK CHAPTER(S) TOPIC
Week One Chapters 1 and 2 Introduction to Network Models
Week Two Chapter 2 Graph Terminology, Data Structures
Week Three Chapter 3 Some Complexity Theory and Graph Search Algorithms
Week Four Chapter 4 Shortest Paths: Label-Setting Algorithms
Week Five Chapter 5 Shortest Paths: Heap Searches and Label-Correcting Algorithms
Week Six Chapter 6 Basic Algorithms for Maximum Flow Problems
Week Seven Chapter 6 (cont) Combinatorial applications of Maximum Flow Problems
Week Eight MIDTERM EXAM
Week Nine Chapter 7 Preflow Push algorithms and Global Min Cut
Week Ten Chapter 9 Minimum Cost Flow Algorithms
Week Eleven Chapter 11 Network Simplex Algorithms
Week Twelve Chapter 13 Minimum Spanning Trees
Week Thirteen Chapter 16 Lagrangian Relaxation
Week Fourteen Review
Week Fifteen Final Exam
Fundamental Rules:
(1) Make-up exams will only be given for extreme situations, and only if I am contacted before the exam is given and full arrangements are established. Full adherence to this policy is the responsibility of the student.
(2) The schedule and exam dates above are tentative, and it is the student's responsibility to keep abreast of changes.
(3) Homework will be assigned each class, and usually collected. All work must be clearly written. Illegible work will not be accepted. Each graded homework assignment will count 10 points.
(4) There is a penalty of 10% of the total grade for each day that the homework is late.
(5) All students are to adher to the George Mason University Honor Code.