ORE 643/SYST 521/SYST420: NETWORK MODELING

Fall 2001

Professor Terry L. Friesz

tel: 703 993 1658

email: tfriesz@gmu.edu

HOMEWORK AND EXAMS:

There will be ten (10) graded homework assignments. Depending on the class performance on the homework, there may also be one (1) midterm and one (1) final exam. These exams will be take-home, open book.

GRADING:

Your grade will be determined by equally weighting your performance on each of the three course requirements: homework, midterm and final. Extra consideration will also be given for classroom participation/facility with the lecture material demonstrated during dialogue with the instructor.

EVALUATION EXAM:

It has unfortunately been the case in past years that some students registering for this course lack the requisite mathematical maturity. For this reason during the first class meeting an “evaluation exam” to test students’ competency in elementary calculus, analysis, linear algebra, linear programming and numerical methods will be assigned as the first homework. It is due at the beginning of the second lecture and will be graded. A threshold score will be stipulated by the instructor. Students scoring below this threshold are strongly urged NOT to take this course for credit since it is unlikely that they will receive a grade of B or higher.

RECOMMENDED TEXT:

1. Bertsekas: Network Optimization, Athena, 1998 (isbn 1-886529-02-7)

RECOMMENDED SOFTWARE: One of the following or an equivalent

1. A Mathematical Programming Language (AMPL) Student Edition Software for Windows, Wadsworth Publishing, 1997 (isbn 0 534 50982 7), or an equivalent full-featured linear programming software package; or

2. General Algebraic Modeling System (GAMS), GAMS Development Corporation, 2000 (http://www.gams.com/)

3. Scientific WorkPlace, MacKichan Software Inc., 2000 (http://www.mackichan.com/)

HONOR CODE AND POLICY OF COLLABORATION:

No collaboration of any kind is allowed on homework or exams. The honor code is continuously in force during this course.

OUTLINE of LECTURES:

1. introduction (Bertsekas, Chapter 1)

1.1 network structure and total unimodularity

1.2 network optimization problem defined

2. the linear minimum cost flow problem (LMCFP) (Bertsekas, Chapter 4)

3. special cases of the LMCFP (Lecture, copycenter notes)

3.1 transportation problem

3.2 shortest path problem

3.3 maximal flow problem

3.4 assignment problem

4. network simplex algorithm (Bertsekas, Chapter 5)

5. labeling algorithms for shortest path problems (Bertsekas, Chapter 2)

5.1 shortest path algorithms

5.2 maximal flow algorithm

6. Ford-Fulkerson algorithm for the maximal flow problem (Bertsekas, Chapter 3)

7. network optimization models with integer variables (Bertsekas, Chapter 10)

7.1 examples

7.1.1 traveling salesman problem

7.1.2 fixed charge problem

7.1.3 optimal trees

7.1.4 matching

7.1.5 arc covering

7.1.6 facility location

7.2 algorithms

7.2.1 branch and bound

7.2.2 relaxation and decomposition

7.2.3 heuristics

8. the nonlinear minimum cost flow problem (NLMCFP) (Bertsekas, Chapter 8)

9. nonlinear optimization models with near network structure (Bertsekas, Chapter 8)

9.1 examples

9.1.1 reservoir control

9.1.2 traffic assignment

9.2 algorithms

9.2.1 relaxation

9.2.2 decomposition

10. mathematical games on networks (Lecture, possible copy center notes8/28/00August 28, 2000)

10.1 the core of a game

10.2 Cournot-Nash noncooperative games

10.3 traffic equilibria and spatial economics

10.4 Stackelberg leader follower games

10.5 network design and market penetration models

10.6 formulation and solution of examples