90-772 Operations Research for the Public Sector

Syllabus06Fall90772.doc

90-772 Operations Research for the Public Sector

H. JohnHeinzIIISchool of Public Policy and Management

CarnegieMellonUniversity

Fall 2006Course Syllabus

1. Course Administration

Course Meetings:

Lectures: M, W1:30 PM – 2:50PM1003Hamburg Hall

Discussion: F 1:30PM – 2:50 PM1003Hamburg Hall

Professor: / Teaching Assistant:
Michael P. Johnson / Changmi Jung
2107C Hamburg Hall / 242 Hamburg Hall
412-268-4270 / 412-268-1846
/
/ N/A
Office Hours:T 11 AM - Noon, F 3 – 4 PM / TBA

Texts:

Required:

• Winston, W.L. and M. Venkataraman. 2003. Introduction to Mathematical Programming. Operations Research: Volume One, Fourth Edition. Pacific Grove, CA: Thompson-Brooks/Cole. Available at CMU bookstore: $120.50 (new), $90.50 (used). Amazon.com: $121.95(new), $35.00 (used). Companion website: (you can order the book direct from the publisher for $109.76)
• Course binder of readings, available from CMU bookstore, $30.

Recommended (available at CMU’s Hunt Library unless otherwise indicated):

• Albright, S.C. 2001. VBA for Modelers: Developing Decision Support Systems with Microsoft Excel. Pacific Grove, CA: Duxbury-Thompson Learning [Not available at CMU or Pitt].
• Cohon, J.L. 1978. Multiobjective Programming and Planning. New York: Academic Press.
• Daskin, M.S. 1995. Network and Discrete Location: Models, Algorithms and Applications. New York: Wiley-Interscience.
• Fourer, R., Gay, D.M. and B.W. Kernighan. 2003. AMPL: A Modeling Language for Mathematical Programming, Second Edition. Pacific Grove, CA: Thompson-Brooks/Cole [Previous edition available at Hunt Library].
• Hillier, F.S. and G.J. Lieberman. 1995. Introduction to Operations Research, Sixth Edition. New York: McGraw-Hill.
• Keeney, R.L. 1992. Value-Focused Thinking: A Path to Creative Decisionmaking. Cambridge, MA: HarvardUniversity Press.
• Pollock, S.M., Rothkopf, M.H. and A. Barnett (eds.) 1994. Handbooks in Operations Research and Management Science, Vol. 6: Operations Research and the Public Sector. Amsterdam: North-Holland.
• Taha, H.A. 2003. Operations Research: An Introduction, 7th Edition. Upper Saddle River, NJ: Prentice-Hall [Previous edition available at Hunt Library].

Software/Internet Resources:

• AMPL. 2006. AMPL: A Modeling Language for Mathematical Programming [free student version; fee-based professional version]. World Wide Web:
• Argonne National Laboratory. 2006. NEOS Server for Optimization [free suite of Web-based math programming solvers]. World Wide Web:
• Beasley, J.L. 2006. OR-Notes. World Wide Web:
• Creative Decisions Foundation. 2006. Super Decisions [free download of Analytic Hierarchy Process multi-criteria decision model; registration required]. World Wide Web:
• Frontline Systems. 2006. Frontline Systems Inc.: Developers of Your Spreadsheet's Solver [fee-based and free software downloads; registration required]. World Wide Web:
• Greenberg, H.J. 2006. Mathematical Programming Glossary. World Wide Web:
• sci.op-research. 2006. Usenet newsgroups. World Wide Web: [OR community discussion group; access via Google.com].
• OptimizationTechnologyCenter of Northwestern University and Argonne National Laboratory. 2005. Linear Programming Frequently Asked Questions. World Wide Web:
• Visual Decision, Inc. 2004.DecisionLab 2000 [free download of PROMETHEE multi-criteria decision model]. World Wide Web:

Course Purpose

Operations research/management science (OR/MS) is an interdisciplinary field that is:

(1)"[A] scientific approach to decision making;

(2)[C]oncerned with scientifically deciding how best to design and operate systems, usually under conditions requiring the allocation of scarce resources" (ORSA 1990, p. 8).

OR/MS (hereafter referred to as OR) uses techniques from organizational management, economics, finance, operations management, mathematics and computer science and other fields to enable firms to deliver serviceefficiently (using as few resources as possible) andeffectively (achieving policy goals and objectives). Whereas economics may provide insight regarding properties of certain given policies, and management information systems may assist micro-level implementation of given policies, OR can help determine exactly what policy to pursue and the estimated impacts associated with alternative policies.

In the public sector, OR can also enable government and nonprofit organizations deliver serviceequitably (ensuring fairness between groups affected by policies). Public sector OR is often used to solve complex problems with multiple stakeholders, multiple objectives and policy, politicalor administrative restrictions on allowable actions.

This course will focus on the development, solution and interpretation of deterministic mathematical programming models for public sector problems. A lesser emphasis will be placed on solution algorithms for math programming models, including optimization methods and heuristics. Very little emphasis will be placed on mathematical proofs of model or algorithm properties.

In addition, because computer-based decision support systems(DSSs) are a primary means by which OR solutions are delivered to end-users, we will devote a small portion of the course to presenting the fundamentals of DSS analysis, design and implementation. We will also discuss methods to solve problems with a relatively small number of pre-defined alternatives incorporating complex decisionmaker preferences, and mathematical programs with multiple objectives, referred to as multi-criteria decision models (MCDMs) and multi-objective decision models (MODMs), respectively.

Course Goals

• Develop expertise in modeling and interpreting the solutions to novel, complex problems, especially those in the public sector;
• Use and understand commercially available algorithms and implement heuristic solution methods;
• Understand policy and organizational implications of public-sector OR models.

Course Prerequisites

Students who take this course should have experience in elementary management science with a spreadsheet emphasis, microeconomics, management information systems, statistics and public policy.

Administrative Details

There will be nine problem sets, a project and a final exam.Excel’s Solver is always acceptable for computational exercises in problem sets and the project. However, other packages such as AMPL, LINDO or LINGO may be used as well to solve mathematical programs. In particular, mathematical programming languages such as AMPL or LINGO may make implementation of large or complex math programs significantly easier than with Solver or LINDO. Software packages such as Super Decisions or Decision Lab 2000 are useful for solving multi-criteria decision models.

All publicly available PCs in the HeinzSchool include the Solver add-in as a feature of Microsoft Excel (but this version is limited to 200 decision variables and 100 constraints). The student versionsof AMPL (limited to 300 decision variables and 300 constraints/objectives), Super Decisions and Decision Lab 2000 are available on the Web (see URLs listed in “Software/Internet Resources”, above). More advanced versions of Solver are available (for a fee) on the Frontline Systems website, The free NEOS Optimization Server will accept math programs of arbitrary size for use with a variety of non-commercial solvers.

Sudent versions of LINGO, LINDO and Premium Solver are available on the CD-ROM included with the Winston and Venkataraman text. The following course software are available on cluster PCs in Hamburg Hall A103: AMPL (student version), Decision Lab 2000, LINDO V6.1 (student version), LINGO V7.0 (student version), Premium Solver for Education and Super Decisions.

All problem sets are due at the start of class unless otherwise specified. The project will focus on modeling, solution and analysis of a student-defined problem in the public sector as well as requirements analysis for a decision support system that implements the OR model. The final exam will be pencil-and-paper only.

Collaboration between students on problem sets is acceptable and encouraged. At most two students may collaborate on problem sets. Whenever collaboration occurs, please indicate which student is responsible for most of a given problem.

Professor Johnson’s faculty assistant is Connie Lucas, 8-8756.Her office is 2112 HbH, directly opposite Prof. Johnson’s office. She will have copies of the course syllabus and the reading packet. She will also have copies of graded homeworks, project deliverables and exams that have not been picked up.

Course grades will be computed based on the following formula:

Homework

/ 35%

Project

/

40%

Final Exam

/

25%

Homeworks, exams and the project may include extra credit portions.

Requests for regrades of any course material may be submitted to the professor. When doing a regrade, the entire homework, exam or case can be examined, and the new grade could be higher or lower than the original grade. All regrades are final.

Students are requested to make appointments for meetings with the professor outside normal office hours.

Course Web Page:

After logging in, choose “F06-90772: F06-Operations Research” from the portion of the page titled “My Courses.”

This Web page is an integrated course management system called Blackboard. All students who are registered for 90-772 may access this page, and use a number of resources, including:

• Course syllabus
• Lecture notes
• Homework assignments
• Data for homework assignments and projects
• Frequently Asked Questions
• Course updates and announcements
• Threaded discussion sections for all course-related concerns
• Links to other Internet resources.

The Blackboard site is intended to enable students to access course information more easily, for the professor and TAs to communicate with students more easily, and for students to help each other master course material more easily than might be the case with a standard course Web page. Therefore, I expect that all students will check the course Web page frequently to stay current with course issues. Please be sure to use the on-line help to familiarize yourself with Blackboard’s features.

All OR students have been registered for the Blackboard site, with username set to the Andrew ID and password set to the first eight digits of the student ID. Please change the default password as soon as possible. Please contact the professor if you have trouble logging in or if you are dropping the course and wish to delete your OR Blackboard account.

Before sending e-mail to TAs or the professor, check the Web site and other students to see if your questions have been already answered!

II.Course Topics and Lecture Plan

Course Topics (27class lectures, 3 tutorials, 1 discussion-based project presentation)

• Introduction to Public-Sector OR: modeling, implementation, policy analysis and public values(3)
• Linear algebra review (1)
• Linear Programming: models/applications, solution methods(4 plus two tutorial sessions)
• Decision models with multiple criteria and objectives(2 plus one tutorial session)
• Linear Programming: sensitivity analysis and duality (3)
• Network LP models (5)
• Integer programming: models, solution methods (3)
• Heuristic and meta-heuristic solution methods (2)
• Location models (3)
• Special topics: Introduction to decision support systems (1)
• Project presentations (1 discussion session)

Lecture Plan

Monday, August 28: / Lecture 1 - Course Introduction

• Topics:

-Student introductions

-Review of syllabus

-Introduction to public-sector OR

• Reading:

-Pollock, S.M. and M.D. Maltz. 1994. “Operations Research in the Public Sector: An Introduction and Brief History”, in (S.M. Pollock, M.H. Rothkopf and A. Barnett, Eds.)Handbooks in Operations Research and Management Science, Vol. 6: Operations Research and the Public Sector. Amsterdam: North-Holland, pp. 1 - 22.

-Winston, W.L. and M. Venkataraman. 2003. Introduction to Mathematical Programming. Operations Research: Volume One, Fourth Edition. Pacific Grove, CA: Thompson-Brooks/Cole, Chapter 1, pp. 1 – 10.

• Problem Set #1 (due Friday, September 8):

-Public-sector OR problem identification and description

-Value-focused thinking

Wednesday, August 30: / Lecture 2 - Public-Sector Implementation of OR and Modeling Principles

• Topics:

-Modeling and policy analysis in public-sector OR

-Use and misuse; understanding and misunderstanding of models

-Links between operations research, economics, policy analysis and planning

• Readings:

-Gass, S.I. 1994. “Public Sector Analysis and Operations Research/Management Science”, in (S.M. Pollock, M.H. Rothkopf and A. Barnett, Eds.)Handbooks in Operations Research and Management Science, Vol. 6: Operations Research and the Public Sector. Amsterdam: North-Holland, pp. 23 - 46.

-Barnett, A. 1994. “Models Fail”, in (S.M. Pollock, M.H. Rothkopf and A. Barnett, Eds.)Handbooks in Operations Research and Management Science, Vol. 6: Operations Research and the Public Sector. Amsterdam: North-Holland, pp. 47 - 66.

-Blumstein, A. 2002. Crime Modeling. Operations Research50(1): 16 – 24.

-Larson, R.C. 2002. Public Sector Operations Research: A Personal Journey. Operations Research50(1): 135 – 145.

Friday, September 1: / Discussion Session
Monday, November 4: / No Lecture (Labor Day)
Wednesday, September 6: / Lecture 3 – Value-Focused Thinking

• Topics:

-Value-focused thinking principles

-Extensions to OR modeling

-Case study: energy planning

• Readings:

-Keeney, R.L. 1996. Value-Focused Thinking: Identifying Decision Opportunities and Creating Alternatives. European Journal of Operational Research92: 537 – 549.

• Problem Set #2 (due Friday, September 15):

-Matrix manipulation

-LP formulations

Friday, September 8: / Discussion Session

• Problem Set #1 due

Monday, September 11: / Lecture 4 - Linear Algebra Review

• Topics:

-Introduction to matrices

-Formulating and solving systems of linear equations

-Linear independence and dependence

-Matrix inversion

• Reading:

-Winston and Venkataraman, Chapter 2, p. 11 – 41, 44 – 46.

Wednesday, September 13: / Lecture 5 - Introduction to Linear Programming

• Topics:

-Formulations

• Giapetto problem
• Diet problem

-Value-based thinking as an aid to formulation of LPs

-LP Characteristics

• Canonical form
• Basis/basic feasible solution
• Slack/surplus/artificial variables
• Infeasible/optimal/unbounded solutions to LPs

• Reading:

-Winston and Venkataraman, p. 49 - 71.

• Problem Set #3 (due Monday, September 25):

-LP formulations

-LP solutions

Friday, September 15: / Tutorial – Solving Linear Programs using Software

• Topics:

-Spreadsheet solvers: Excel's Solver

-Math programming languages: AMPL, LINDO, LINGO

• Readings:

-Winston and Venkataraman, Section 4.17, p. 202 – 210, Sections 4.9 – 4.10, p. 158 – 167.

-Fourer, R., Gay, D.M. and B.W. Kernighan. 2003. AMPL: A Modeling Language for Mathematical Programming, Second Edition. Pacific Grove, CA: Thompson-Brooks/Cole, p. 1 - 20.

• Problem Set #2 due

Monday, September 18: / Lecture 6 - LP Formulation Techniques

• Topics:

-Min-max/max-min formulations

-Absolute value formulations

-Multiple time periods

-Piecewise-linear formulations

• Reading:

-Winston and Venkataraman, p. 72 - 113.

Wednesday, September 20: / Lecture 7 - LP Applications

• Topics:

-Work Scheduling

-Capital budgeting

-Land use planning

Friday, September 22: / Tutorial – Solving Linear Programs using Software (continued)
Monday, September 25: / Lecture 8 – Decision Models with Multiple Criteria

• Topics:

-Introduction to decision rules

• Multi-attribute decision models
• Multi-objective decision models

-Multi-Attribute Decision Models:

• Additive weighting methods
• Value/utility functions
• Analytic Hierarchy process

• Readings:

Cohon, J.L. 1978. Multiobjective Programming and Planning. New York: Academic Press, p. 13 - 26, 85 - 97.

Von Winterfeldt, D. and W. Edwards. 1986. Decision Analysis and Behavioral Research. Cambridge: CambridgeUniversity Press, p. 259 – 313.

Saaty, T.L. 1994. How to Make a Decision: The Analytic Hierarchy Process. Interfaces24(6): 19 – 43.

• Problem Set #3 due
• Problem Set #4 (due Monday, October 2):

-Multi-objective linear programming

-Multi-criteria decision models

Wednesday, September 27: / Lecture 9 – Decision Models with Multiple Criteria (continued)

• Topics:

-Multi-Attribute Decision Models (continued):

• Concordance methods (ELECTRE, PROMETHEE)

-Multi-Objective Decision Models:

• Generation methods
• Compromise programming

• Readings:

Roy, B. 1991. The Outranking Approach and the Foundations of Electre Methods. Theory and Decision31: 49 – 73.

Brans, J.P. and Ph. Vincke. 1985. A Preference Ranking Organisation Method: (The PROMETHEE Method for Multiple Criteria Decision-Making) Management Science31(6): 674 – 656.

Cohon, p. 98 - 126.

Friday, September 29: / Tutorial – Solving MOLP and MCDM using Software

• Topics:

-Spreadsheet solvers for multiobjective LPs: Excel's Solver

-MCDM software: Super Decisions, Decision Lab

Monday, October 2: / Lecture 10 – Linear Programming Extensions

• Topics:

-Fractional programming and Data Envelopment Analysis

-Motivation and illustration of Simplex Method

-Revised Simplex Method

• Readings:

-Winston and Venkataraman, Section 6.12, p. 335 - 340.

-Sherman, H.D. and G. Ladino. 1995. Managing Bank Productivity Using Data Envelopment Analysis (DEA). Interfaces25(2): 60 – 73.

-Taha, H.A. 2003. Operations Research: An Introduction, 7th Edition. Upper Saddle River, NJ: Prentice-Hall, p. 289 – 303.

• Problem Set #4 due
• Problem Set #5 (due Monday, October 16):

-Sensitivity analysis

-LP Duality

Wednesday, October 4: / Lecture 11 - Sensitivity Analysis

• Topics:

-Shadow prices and right-hand side ranges

-Reduced costs and objective function coefficient ranges

-Sequences of parameter changes

• Reading:

-Winston and Venkataraman, Chapter 5, p. 227 - 254.

• Course Project (due Friday, December 8):

-Problem description

-Model(s)

-Data

-Solution method(s)

-Decision support system requirements

Friday, October 6: / Discussion Session
Monday, October 9: / Lecture 12 – Sensitivity Analysis, Continued

• Topics:

-Changing the column of a nonbasic variable

-New activities

-Changing multiple parameters simultaneously (100% rule)

-Tradeoff curves

-Spider plots and Tornado diagrams

• Readings:

-Winston and Venkataraman, Sections 6.3 – 6.4, p. 285 - 294.

-Eisenbach, T.G. 1992. Spiderplots versus Tornado Diagrams for Sensitivity Analysis. Interfaces22(6): 40-46.

Wednesday, October 11: / Lecture 13- LP Duality Theory

•Topics:

-Primal/dual equivalency

-Economic interpretations of dual

-Important duality theorems

-Complementary slackness

• Readings:

-Winston and Venkataraman, Sections 6.5 – 6.7, pp. 295 - 307 (omit proofs), Section 6.10, pp. 325 - 328.

Friday, October 13: / Discussion Session
Monday, October 16: / Lecture 14 - Network Flows Introduction

• Topics:

-Nodes, arcs, flows

-Complete graphs, bipartite graphs, trees, paths

-Minimum spanning tree problem

• Reading:

Bertsekas, D.P. 1998. Network Optimization: Continuous and Discrete Models. Belmont, Mass.: Athena Scientific, p. 1 – 20.

Winston and Venkataraman, Section 8.1, p. 413 – 414, Section 8.6, p. 456 – 458.

• Problem Set #5 due
• Problem Set #6 (due Monday, October 30):

-Network flows

Wednesday, October 18: / Lecture 15 - Network Flows, Continued

• Topics:

-Transportation problem

-Multicommodity flow problem

-Assignment problem

• Readings:

Winston and Venkataraman, Section 7.1, p. 360 – 371, Section 7.5, p. 393 – 394.

Friday, October 20: / No Discussion Session (mid-semester break)
Monday, October 23: / Lecture 16 - Network Flows, Continued

• Topics:

-Transshipment problem

-Shortest Path problem

-Maximum Flow problem

• Reading:

Winston and Venkataraman, Sections 7.6, p. 400 - 403, 8.2 - 8.3, p. 414 - 431.

Wednesday, October 25: / Lecture 17 - Network Flows, Continued

• Topics:

-PERT/CPM

-Minimum Cost Flow problem

-Maximum Flow problem

• Reading:

Winston and Venkataraman, Sections8.4 - 8.5, pp. 431 - 454.

Friday, October 27: / Discussion Session
Monday, October 30: / Lecture 18 - Network Flows Applications (Rema Padman, guest lecturer)

• Problem Set #6 due

Wednesday, November 1: / Lecture 19 - Integer Programming Introduction and Formulations

• Topics:

Introduction to IP

Formulation methods:

▪If-then constraints

▪Fixed-charges

▪Either-or constraints

▪Piecewise-linear functions

▪Functions with N possible values

▪M out of N constraints must hold

▪Converting general integer decision variables to binary decision variables

• Reading:

Winston and Venkataraman, Sections 9.1 – 9.2, p. 475 – 502, Section 9.6, p. 534 - 545.

• Problem Set #7 (due Wednesday, November 15):

Integer programs

Combinatorial optimization problems