90772 Operations Research for the Public Sector
H. John Heinz III School of Public Policy and Management
Carnegie Mellon University
Fall 2006 Course Syllabus

Course Administration
Course Meetings:
Lectures: M, W 1:30 PM – 2:50 PM 1003 Hamburg Hall
Discussion: F 1:30 PM – 2:50 PM 1003 Hamburg Hall
Professor:

Teaching Assistant:

Michael P. Johnson

Changmi Jung

2107C Hamburg Hall

242 Hamburg Hall

4122684270

4122681846

johnson2@andrew.cmu.edu

changmi@andrew.cmu.edu

http://www.heinz.cmu.edu/bio/faculty/johnson2.html

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: ThompsonBrooks/Cole. Available at CMU bookstore: $120.50 (new), $90.50 (used). Amazon.com: $121.95 (new), $35.00 (used). Companion website: http://www.brookscole.com/cgiwadsworth/course_products_wp.pl?fid=M2b&product_isbn_issn=0534359647&discipline_number=17# (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: DuxburyThompson 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: WileyInterscience.

Fourer, R., Gay, D.M. and B.W. Kernighan. 2003. AMPL: A Modeling Language for Mathematical Programming, Second Edition. Pacific Grove, CA: ThompsonBrooks/Cole [Previous edition available at Hunt Library].

Hillier, F.S. and G.J. Lieberman. 1995. Introduction to Operations Research, Sixth Edition. New York: McGrawHill.

Keeney, R.L. 1992. ValueFocused Thinking: A Path to Creative Decisionmaking. Cambridge, MA: Harvard University 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: NorthHolland.

Taha, H.A. 2003. Operations Research: An Introduction, 7^{th} Edition. Upper Saddle River, NJ: PrenticeHall [Previous edition available at Hunt Library].
Software/Internet Resources:

AMPL. 2006. AMPL: A Modeling Language for Mathematical Programming [free student version; feebased professional version]. World Wide Web: http://www.ampl.com/DOWNLOADS/index.html.

Argonne National Laboratory. 2006. NEOS Server for Optimization [free suite of Webbased math programming solvers]. World Wide Web: http://wwwneos.mcs.anl.gov/.

Beasley, J.L. 2006. ORNotes. World Wide Web: http://people.brunel.ac.uk/~mastjjb/jeb/or/contents.html.

Creative Decisions Foundation. 2006. Super Decisions [free download of Analytic Hierarchy Process multicriteria decision model; registration required]. World Wide Web: http://www.superdecisions.com/.

Frontline Systems. 2006. Frontline Systems Inc.: Developers of Your Spreadsheet's Solver [feebased and free software downloads; registration required]. World Wide Web: http://www.solver.com/.

Greenberg, H.J. 2006. Mathematical Programming Glossary. World Wide Web: http://glossary.computing.society.informs.org/.

sci.opresearch. 2006. Usenet newsgroups. World Wide Web: http://groupsbeta.google.com/group/sci.opresearch?hl=en [OR community discussion group; access via Google.com].

Optimization Technology Center of Northwestern University and Argonne National Laboratory. 2005. Linear Programming Frequently Asked Questions. World Wide Web: http://wwwunix.mcs.anl.gov/otc/Guide/faq/linearprogrammingfaq.html.

Visual Decision, Inc. 2004. Decision Lab 2000 [free download of PROMETHEE multicriteria decision model]. World Wide Web: http://www.visualdecision.com/download.htm.
Course Purpose
Operations research/management science (OR/MS) is an interdisciplinary field that is:

"[A] scientific approach to decision making;

[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 service efficiently (using as few resources as possible) and effectively (achieving policy goals and objectives). Whereas economics may provide insight regarding properties of certain given policies, and management information systems may assist microlevel 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 service equitably (ensuring fairness between groups affected by policies). Public sector OR is often used to solve complex problems with multiple stakeholders, multiple objectives and policy, political or 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 computerbased decision support systems (DSSs) are a primary means by which OR solutions are delivered to endusers, 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 predefined alternatives incorporating complex decisionmaker preferences, and mathematical programs with multiple objectives, referred to as multicriteria decision models (MCDMs) and multiobjective 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 publicsector 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 multicriteria decision models.
All publicly available PCs in the Heinz School include the Solver addin as a feature of Microsoft Excel (but this version is limited to 200 decision variables and 100 constraints). The student versions of 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, www.solver.com. The free NEOS Optimization Server will accept math programs of arbitrary size for use with a variety of noncommercial solvers.
Sudent versions of LINGO, LINDO and Premium Solver are available on the CDROM 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 studentdefined 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 pencilandpaper 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, 88756. 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:
http://blackboard.andrew.cmu.edu
After logging in, choose “F0690772: F06Operations 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 90772 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 courserelated 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 online 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 email 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 (27 class lectures, 3 tutorials, 1 discussionbased project presentation)

Introduction to PublicSector 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 metaheuristic 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
 
Student introductions

Review of syllabus

Introduction to publicsector OR

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: NorthHolland, pp. 1  22.

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

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

Publicsector OR problem identification and description

Valuefocused thinking
Wednesday, August 30:

Lecture 2  PublicSector Implementation of OR and Modeling Principles
 
Modeling and policy analysis in publicsector OR

Use and misuse; understanding and misunderstanding of models

Links between operations research, economics, policy analysis and planning

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: NorthHolland, 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: NorthHolland, pp. 47  66.

Blumstein, A. 2002. Crime Modeling. Operations Research 50(1): 16 – 24.

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

Discussion Session

Monday, November 4:

No Lecture (Labor Day)

Wednesday, September 6:

Lecture 3 – ValueFocused Thinking
 
Valuefocused thinking principles

Extensions to OR modeling

Case study: energy planning

Keeney, R.L. 1996. ValueFocused Thinking: Identifying Decision Opportunities and Creating Alternatives. European Journal of Operational Research 92: 537 – 549.

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

Matrix manipulation

LP formulations
Friday, September 8:

Discussion Session

Monday, September 11:

Lecture 4  Linear Algebra Review
 
Introduction to matrices

Formulating and solving systems of linear equations

Linear independence and dependence

Matrix inversion

Winston and Venkataraman, Chapter 2, p. 11 – 41, 44 – 46.
Wednesday, September 13:

Lecture 5  Introduction to Linear Programming
 
Giapetto problem

Diet problem

Valuebased thinking as an aid to formulation of LPs

Canonical form

Basis/basic feasible solution

Slack/surplus/artificial variables

Infeasible/optimal/unbounded solutions to LPs

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
 
Spreadsheet solvers: Excel's Solver

Math programming languages: AMPL, LINDO, LINGO

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: ThompsonBrooks/Cole, p. 1  20.
Monday, September 18:

Lecture 6  LP Formulation Techniques
 
Minmax/maxmin formulations

Absolute value formulations

Multiple time periods

Piecewiselinear formulations

Winston and Venkataraman, p. 72  113.
Wednesday, September 20:

Lecture 7  LP Applications
 
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
 
Introduction to decision rules

Multiattribute decision models

Multiobjective decision models

MultiAttribute Decision Models:

Additive weighting methods

Value/utility functions

Analytic Hierarchy process

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: Cambridge University Press, p. 259 – 313.

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

Problem Set #3 due

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

Multiobjective linear programming

Multicriteria decision models
Wednesday, September 27:

Lecture 9 – Decision Models with Multiple Criteria (continued)
 
MultiAttribute Decision Models (continued):

Concordance methods (ELECTRE, PROMETHEE)

MultiObjective Decision Models:

Generation methods

Compromise programming

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

Brans, J.P. and Ph. Vincke. 1985. A Preference Ranking Organisation Method: (The PROMETHEE Method for Multiple Criteria DecisionMaking) Management Science 31(6): 674 – 656.

Cohon, p. 98  126.
Friday, September 29:

Tutorial – Solving MOLP and MCDM using Software
 
Spreadsheet solvers for multiobjective LPs: Excel's Solver

MCDM software: Super Decisions, Decision Lab
Monday, October 2:

Lecture 10 – Linear Programming Extensions
 
Fractional programming and Data Envelopment Analysis

Motivation and illustration of Simplex Method

Revised Simplex Method

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

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

Taha, H.A. 2003. Operations Research: An Introduction, 7^{th} Edition. Upper Saddle River, NJ: PrenticeHall, 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
 
Shadow prices and righthand side ranges

Reduced costs and objective function coefficient ranges

Sequences of parameter changes

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
 
Changing the column of a nonbasic variable

New activities

Changing multiple parameters simultaneously (100% rule)

Tradeoff curves

Spider plots and Tornado diagrams

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

Eisenbach, T.G. 1992. Spiderplots versus Tornado Diagrams for Sensitivity Analysis. Interfaces 22(6): 4046.
Wednesday, October 11:

Lecture 13 LP Duality Theory

• Topics:

Economic interpretations of dual

Important duality theorems

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
 
Nodes, arcs, flows

Complete graphs, bipartite graphs, trees, paths

Minimum spanning tree problem

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):

Transportation problem

Multicommodity flow problem

Assignment problem

Winston and Venkataraman, Section 7.1, p. 360 – 371, Section 7.5, p. 393 – 394.
Friday, October 20:

No Discussion Session (midsemester break)

Monday, October 23:

Lecture 16  Network Flows, Continued
 
Transshipment problem

Shortest Path problem

Maximum Flow problem

Winston and Venkataraman, Sections 7.6, p. 400  403, 8.2  8.3, p. 414  431.
Wednesday, October 25:

Lecture 17  Network Flows, Continued
 
PERT/CPM

Minimum Cost Flow problem

Maximum Flow problem

Winston and Venkataraman, Sections 8.4  8.5, pp. 431  454.
Friday, October 27:

Discussion Session

Monday, October 30:

Lecture 18  Network Flows Applications (Rema Padman, guest lecturer)

Wednesday, November 1:

Lecture 19  Integer Programming Introduction and Formulations
 
Introduction to IP

Formulation methods:

Ifthen constraints

Fixedcharges

Eitheror constraints

Piecewiselinear functions

Functions with N possible values

M out of N constraints must hold

Converting general integer decision variables to binary decision variables

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
Friday, November 3:

Discussion Session

Monday, November 6:

No Lecture (conference travel)

Wednesday, November 8:

Lecture 20  Integer Programming Model Classes
 
Garfinkel, R.S. 1985. “Motivation and Modeling”, in (E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, Eds.) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Chichester: John Wiley and Sons, p. 17  36.

Christofides, N. 1985. “Vehicle Routing”, in (E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, Eds.) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Chichester: John Wiley and Sons, p. 431  448.
Friday, November 10:

Discussion Session

Monday, November 13:

Lecture 21 – Integer Programming Model Classes (continued) and Solving General IPs
 
Reformulations

Branchandbound method

Other optimizationbased strategies:

Lagrangean relaxation

Cutting planes

Column generation

Winston and Venkataraman, Sections 9.3 – 9.5, p. 512 – 534.

Barnhart, C., Johnson, E.L., Nemhauser, G.L., Sigismondi, G. and P. Vance. 1993. Formulating a MixedInteger Programming Problem to Improve Solvability. Operations Research 41(6): 1013 – 1019.
Wednesday, November 15:

Lecture 22 –Heuristic and MetaHeuristic Solution Methods (Hakan Yildiz, Guest Lecturer)
 
Introduction to heuristic methods

Local heuristics:

Greedy heuristics

Local improvement heuristics

Global (Meta) heuristics:

Genetic algorithms and the Evolutionary Solver

Winston and Venkataraman, Sections 14.2, 14.3, p. 804 – 808; 15.1 – 15.2, pp. 823 – 835

Problem Set #8 (due Monday, November 27):

Heuristic and metaheuristic solution methods
Friday, November 17:

Discussion Session

Monday, November 20:

Lecture 23  Heuristic and MetaHeuristic Solution Methods (continued)
 
Topics:

Global (Meta) heuristics (continued):

Simulated annealing

Tabu search

Comparison of metaheuristic methods

Reading:

Winston and Venkataraman, Sections 14.3, 14.5 – 14.6, pp. 805 – 808, 815 – 821.
Wednesday, November 22:

No lecture (Thanksgiving break)

Friday, November 24:

No discussion (Thanksgiving break)

Monday, November 27:

Lecture 24  Introduction to Location Models; Planar Location Models
 
Fitzsimmons, J.A. and M.J. Fitzsimmons. 1998. Service Management: Operations, Strategy, and Information Technology. Boston: McGrawHill, p. 161  187.

Problem Set #8 due

Problem Set #9 (due Wednesday, December 6):

Location on a plane

Location on networks
Wednesday, November 29:

Lecture 25 – Network Location Models
 
Set Covering Problem and extensions

Center and Median Problems

Current, J., Daskin, M. and D. Schilling. 2002. “Discrete Network Location Models”, in (Z. Drezner and H.W. Hamacher, Eds.) Facility Location: Applications and Theory. Berlin: Springer, p. 81 – 117.
Friday, December 1:

Discussion Session

Monday, December 4:

Lecture 26 – Network Location Models (continued)
 
Center and Median Problems

Fixed Charge Facility Location Problems

Obnoxious/Undesirable Facility Location Problems

Current, Daskin and Schilling, continued.

Erkut, E. and S. Neuman. 1989. Analytical Models for Locating Undesirable Facilities. European Journal of Operational Research 40: 275 – 291.
Wednesday, December 6:

Lecture 27  Introduction to Decision Support Systems
 
Review of information system categories

Highlevel DSS architecture

DSS platforms

ECommerce DSS applications

Final exam review

Drudzel, M.J. and R.R. Flynn. 2000. “Decision Support Systems.” Pittsburgh: University of Pittsburgh, School of Information Sciences and Intelligent Systems Program.

Bhargarva, H.K., Sridhar, S. and C. Herrick. 1999. Beyond Spreadsheets: Tools for Building Decision Support Systems. Computer, March 1999, pp. 3139.

Zobel, C., Ragsdale, C. and L. Rees. 2000. HandsOn Learning Experience. OR/MS Today 27(6): 28 – 31.

Geoffrion, A. and R. Krishnan. 2001. Prospects for Operations Research in the EBusiness Era. Interfaces, 31(2): 6 – 36.
Friday, December 8:

Discussion Session
 
Project due (student presentations)
Monday, December 12 – Tuesday, December 13, Thursday, December 15 – Friday, December 16: Heinz School Final Exams
Reference:
Operations Research Society of America (ORSA). 1990. Careers in Operations Research.
90772 Syllabus Fall 06 01/27/17
Share with your friends: 