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: __http://iris.gmu.edu/~khoffman/hoffman.html
__

**All lecture notes, homework assignments, the
posting of grades, etc will appear at: **__http://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: 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: * 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 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.