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

1. 
   Course Administration
   

• 
  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: http://www.brookscole.com/cgi-wadsworth/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.
  

• 
  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: 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: North-Holland.
  
• 
  Taha, H.A. 2003. Operations Research: An Introduction, 7^th Edition. Upper Saddle River, NJ: Prentice-Hall [Previous edition available at Hunt Library].
  

• 
  AMPL. 2006. AMPL: A Modeling Language for Mathematical Programming [free student version; fee-based professional version]. World Wide Web: http://www.ampl.com/DOWNLOADS/index.html.
  
• 
  Argonne National Laboratory. 2006. NEOS Server for Optimization [free suite of Web-based math programming solvers]. World Wide Web: http://www-neos.mcs.anl.gov/.
  
• 
  Beasley, J.L. 2006. OR-Notes. 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 multi-criteria decision model; registration required]. World Wide Web: http://www.superdecisions.com/.
  
• 
  Frontline Systems. 2006. Frontline Systems Inc.: Developers of Your Spreadsheet's Solver [fee-based 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.op-research. 2006. Usenet newsgroups. World Wide Web: http://groups-beta.google.com/group/sci.op-research?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://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html.
  
• 
  Visual Decision, Inc. 2004. Decision Lab 2000 [free download of PROMETHEE multi-criteria decision model]. World Wide Web: http://www.visualdecision.com/download.htm.
  

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

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 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.

• 
  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.
  

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

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 Heinz School 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 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 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%

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 “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.
  

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!

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

• 
  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
  

• 
  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 Research 50(1): 16 – 24.
  
• 
  Larson, R.C. 2002. Public Sector Operations Research: A Personal Journey. Operations Research 50(1): 135 – 145.
  

• 
  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 Research 92: 537 – 549.
  

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

• 
  Matrix manipulation
  
• 
  LP formulations
  

• 
  Problem Set #1 due
  

• 
  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.
  

• 
  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
  

• 
  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
  

• 
  Topics:
  

• 
  Min-max/max-min formulations
  
• 
  Absolute value formulations
  
• 
  Multiple time periods
  
• 
  Piecewise-linear formulations
  

• 
  Reading:
  

• 
  Winston and Venkataraman, p. 72 - 113.
  

• 
  Topics:
  

• 
  Work Scheduling
  
• 
  Capital budgeting
  
• 
  Land use planning
  

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

• 
  Multi-objective linear programming
  
• 
  Multi-criteria decision models
  

• 
  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 Decision 31: 49 – 73.
  
• 
  Brans, J.P. and Ph. Vincke. 1985. A Preference Ranking Organisation Method: (The PROMETHEE Method for Multiple Criteria Decision-Making) Management Science 31(6): 674 – 656.
  
• 
  Cohon, p. 98 - 126.
  

• 
  Topics:
  

• 
  Spreadsheet solvers for multiobjective LPs: Excel's Solver
  
• 
  MCDM software: Super Decisions, Decision Lab
  

• 
  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). Interfaces 25(2): 60 – 73.
  

• 
  Taha, H.A. 2003. Operations Research: An Introduction, 7^th 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
  

• 
  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
  

• 
  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. Interfaces 22(6): 40-46.
  

• 
  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.
  

• 
  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
  

• 
  Topics:
  

• 
  Transportation problem
  
• 
  Multicommodity flow problem
  
• 
  Assignment problem
  

• 
  Readings:
  

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

• 
  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.
  

• 
  Topics:
  

• 
  PERT/CPM
  
• 
  Minimum Cost Flow problem
  
• 
  Maximum Flow problem
  

• 
  Reading:
  

• 
  Winston and Venkataraman, Sections 8.4 - 8.5, pp. 431 - 454.
  

• 
  Problem Set #6 due
  

• 
  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
  

• 
  Topics:
  

• 
  Pure network problems
  
• 
  Location problems
  
• 
  Knapsack problem
  
• 
  The traveling salesman problem
  
• 
  Vehicle routing/scheduling
  

• 
  Readings:
  

• 
  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.
  

• 
  Topics:
  

• 
  Model classes
  

• 
  Machine Scheduling
  

• 
  Solution Methods
  

• 
  Reformulations
  
• 
  Branch-and-bound method
  

• 
  Other optimization-based strategies:
  

• 
  Lagrangean relaxation
  
• 
  Cutting planes
  
• 
  Column generation
  

• 
  Readings:
  

• 
  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 Mixed-Integer Programming Problem to Improve Solvability. Operations Research 41(6): 1013 – 1019.
  

• 
  Topics:
  

• 
  Introduction to heuristic methods
  
• 
  Local heuristics:
  

• 
  Greedy heuristics
  
• 
  Local improvement heuristics
  

• 
  Global (Meta) heuristics:
  

• 
  Genetic algorithms and the Evolutionary Solver
  

• 
  Reading:
  

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

• 
  Problem Set #7 due
  

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

• 
  Heuristic and meta-heuristic solution methods
  

1. 
   Topics:
   
   • 
     Global (Meta) heuristics (continued):
     
     • 
       Simulated annealing
       
     • 
       Tabu search
       
   • 
     Comparison of metaheuristic methods
     
2. 
   Reading:
   
   • 
     Winston and Venkataraman, Sections 14.3, 14.5 – 14.6, pp. 805 – 808, 815 – 821.
     

• 
  Topics:
  

• 
  Introduction
  

• 
  Location on a plane
  

• 
  Readings:
  

• 
  Fitzsimmons, J.A. and M.J. Fitzsimmons. 1998. Service Management: Operations, Strategy, and Information Technology. Boston: McGraw-Hill, p. 161 - 187.
  

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

• 
  Location on a plane
  
• 
  Location on networks
  

• 
  Topics:
  

• 
  Set Covering Problem and extensions
  
• 
  Center and Median Problems
  

• 
  Readings:
  

• 
  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.
  

• 
  Topics:
  

• 
  Center and Median Problems
  

• 
  Fixed Charge Facility Location Problems
  

• 
  Obnoxious/Undesirable Facility Location Problems
  

• 
  Readings:
  

• 
  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.
  

• 
  Topics:
  

• 
  Review of information system categories
  
• 
  High-level DSS architecture
  
• 
  DSS platforms
  
• 
  E-Commerce DSS applications
  
• 
  Final exam review
  

• 
  Reading:
  

• 
  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. 31-39.
  
• 
  Zobel, C., Ragsdale, C. and L. Rees. 2000. Hands-On Learning Experience. OR/MS Today 27(6): 28 – 31.
  
• 
  Geoffrion, A. and R. Krishnan. 2001. Prospects for Operations Research in the E-Business Era. Interfaces, 31(2): 6 – 36.
  

• 
  Problem Set #9 due.
  

• 
  Project due (student presentations)
  

Operations Research Society of America (ORSA). 1990. Careers in Operations Research.