SYST420/ SYST521/OR643

Network Modeling

Systems Engineering and Operations Research Department

George Mason University

Mondays, 4:30-7:10p.m.
Innovation Hall Room 203

Professor Karla L. Hoffman
Office: SciTech Building II, Room 123
Phone: (703)993-1679(direct) or 993-1670 (office)
Homepage for Course:

All lecture notes, homework assignments, the posting of grades, etc will appear at:

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: 1:00-3:00p.m.and by appointment
I am usually on Mondays and Wednesdays from 9:30 to 6:30. I can also be available after class on Mondays.

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:

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      35% homework

l      30% midterm

l      35% 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.