Operations Research

Course number: CO-583-A

Jacobs University, Fall 2021

News

• On the first three Mondays in December (Dec 6, 13, and 20), the TAs will offer question sessions during the regular tutorial times 20:45-22:00 online on MS Teams.
• See here for the final examination schedule. The final exam is scheduled for Dec 22, 9:00 - 11:00. The make-up exam is on Jan 26, 17:00 - 19:00.
• The mock midterm takes place on October 26 during the class session. The midterm will be in-person only (i.e., you only possibly receive bonus points if you write the midterm in person). However, I will put the midterm online as well, and the solutions will be discussed in the tutorial on November 1. See here for practice exams from previous classes.
• Note: the class on Thursday, Sep. 23, will be in the Research II Lecture Hall.
• Note: the class on Tuesday, Sep. 21, will only be from 16:15 - 17:00.
• For September, the regular tutorial will take place on Mondays, 20:45 - 22:00, online on MS Teams (starting on Sep 13). (We will try to find a better time for October/November.)
• See here for the homework sheets.
• There will be one review tutorial on Thursday, September 9, from 19:30 - 20:30, online via MS Teams. Topics will be: inequalities, the equations of lines, basic matrix/vector manipulation, basic Gaussian elimination.
• First class is on Thursday, Sep. 2, in the ICC-West Wing Conference Hall. If you plan to take this class, but could not register yet, please come anyway. This class is offered in person by default and I highly encourage you to come to class if you can. However, I will also record the class sessions on MS Teams, and the lecture notes (and more material) can be found on this website.

Contact Information

Time and Place

First class session: Sep. 2, 2021; last class session: Dec. 2, 2021.

Syllabus

All the most recent information about class can be found on this website.

Official Course Description

Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations. By employing techniques such as mathematical modeling, statistical analysis, and mathematical optimization, operations research finds optimal or near-optimal solutions to complex decision-making problems. Operations Research is concerned with determining the maximum (of profit, performance, or yield) or the minimum (of loss, risk, or cost) of some real-world objective. This module introduces students to modelling of decision problems and the use of quantitative methods and techniques for effective decision-making.

Resources

• MS Teams channel for class recordings and online tutorials.
• Moodle for homework submissions
• Some standard vector and matrix manipulation, and single and multi-variable calculus is assumed as background knowledge for this class. I have taught the classes Advanced Calculus and Calculus and Linear Algebra II before, which were a bit more advanced than the Applied Calculus class in the GEM curriculum. Still the lecture notes on the websites might serve as suitable references.
• Practical Guide to the Simplex Method of Linear Programming by Marcel Oliver. These are notes about linear programming from a previous class. (Note that the standard form of an LP problem and the associated simplex tableau is different from the presentation in Hillier and Lieberman.)
• Chapter 4 on Duality by Van Roy and Mason, Stanford University, is one of the few good introductions to duality theory as it contains a clean conceptual motivation as well as elegant mathematics.
• Operations Research Fall 2020, taught by Marcel Oliver, with lots of material, notes, and practice exams.
• Here are more links to midterm and final exams (and their solutions) from previous classes: Spring 2016, Fall 2016, Fall 2017, Fall 2020.
• Programming:
  • A good python developing environment for scientific applications is Anaconda (Individual Edition). Anaconda contains several programs; for us the most important ones are: Jupyter Notebooks (to create nicely structured and commented code; very good for student projects; Browser based), and Spyder (a standard python editor).
  • The pyomo library can be downloaded for Anaconda here. On the pyomo website you can find general installation instructions and a good documentation.
  • For solving Linear Programming and related problems, we need an additional package. A good one is glpk (GNU Linear Programming Kit). It can be downloaded for Anaconda here.
  • Summary: Download Anaconda, then install pyomo, then install glpk.
  • The Interior Point Optimizer can be downloaded for Anaconda here.

Textbooks

Most of the class material is similar to the following textbook:

• Hillier, Lieberman - Introduction to Operations Research (McGraw-Hill; I use the 9th ed., 2010).

A good textbook on Pyomo is:

• Hart, Laird, Watson, Woodruff - Pyomo - Optimization Modeling in Python (Springer; I use the 1st ed., 2012).

Grading

The assessment for this class is the final exam only. There is a possibility to get bonus points, see below.

Exams

There will be a final exam, which is scheduled centrally in the exam period (Dec. 11 - 22, 2021). As practice (and to obtain bonus points), there will also be a midterm exam (see class schedule below).

Final Exam Preparation

The best exam preparation is to work on and understand the homework problems, plus the examples we have discussed in class. The following final exams from previous years can be used for further practice and cover mostly the same topics as we have done:

Fall 2017: final exam, solutions
Fall 2020: final exam, solutions

Homework Sheets

Usually once per week there will be a homework assignment. The due date is usually one week after it has been handed out, and is stated on each homework sheet. The submission is only electronically via Moodle. Note: It is encouraged to discuss the exercise sheets with your classmates (e.g., discuss how to come up with the solution or what the right way of approaching the problem is). On the other hand, the solutions must be written down and handed in individually! Copying the solutions from somebody else is a violation of Academic Integrity! Please be aware that the Code of Academic Integrity applies to all homework submission, the midterm, and the final! Working on and understanding the homework problems is the best preparation for the final exam.

Bonus points: Solving the homework sheets and the midterm exam can give you bonus points for the final grade. Each of them can provide a bonus of up to 5% (i.e., 0.33 grade points), for a maximum total of 10% (0.67 grade points). The bonus is computed as follows: Take the percentage score above 50% (for each the midterm and the total homework score), and divide by 10. For the computation of the total homework score, the two worst homework sheets will be disregarded. (Note that this implies that there will be no extension of homework submission deadlines!). Note that the maximum final module grade is 100% (even if the bonus would get you above 100%). Important: The bonus cannot change a failing grade into a non-failing grade.

Example: Student A had 80% on the midterm, and a homework average of 45%. The bonus for the midterm is 3%, and there is no bonus for the homework. If the final exam score is 70%, then the total grade is 73%. Example 2: Student B has 50% on the midterm and 100% on the homework. If the final exam score is 40%, then the class would be failed. (The bonus of 5% from the homework is not allowed to be counted.)

Date	Sheet Number	Due Date
Sep 07, 2021	Sheet 1	Sep 14, 2021
Sep 13, 2021	Sheet 2	Sep 20, 2021
Sep 20, 2021	Sheet 3	Sep 27, 2021
Sep 27, 2021	Sheet 4	Oct 04, 2021
Oct 04, 2021	Sheet 5	Oct 11, 2021
Oct 11, 2021	Sheet 6	Oct 18, 2021
Oct 18, 2021	Sheet 7	Oct 25, 2021
Nov 01, 2021	Sheet 8	Nov 08, 2021
Nov 08, 2021	Sheet 9	Nov 15, 2021
Nov 15, 2021	Sheet 10	Nov 22, 2021
Nov 22, 2021	Sheet 11	Nov 29, 2021

Table of Contents

Chapter 1: Introduction

Chapter 2: Linear Programming
2.1: Graphical Solutions
2.2: Standard Form of LP Problems
2.3: The Simplex Method
2.4: The Dual LP Problem
2.5: Transportation Problems
2.6: Network Optimization

Chapter 3: Further Optimization Techniques
3.1: Dynamic Programming
3.2: Decision Analysis
3.3: Inventory Theory
3.4: Nonlinear Programming

Class Schedule

Will be updated while class is progressing.

Below, please click on the date to download the lecture notes of that day.

Note that the book references given below offer only a rough orientation. Sometimes, only parts of a particular chapter are covered in class. Note that the Hillier/Lieberman chapters refer to the ninth edition.

Date	Topics
Sep. 02, 2021	Organization, Introduction, a first example of a linear programming problem See the information on this website for class organization; Hillier/Lieberman: see Chapter 1 and 2 for a general introduction to OR; see Chapter 3.1 for the Wyndor example.
Sep. 07, 2021	Linear Programming: Graphical Solution See R. Larson, Elementary Linear Algebra, Chapter 9.2; also: Hillier/Lieberman Chapter 3.2
Sep. 09, 2021	Standard form of an LP problem, slack variables, short review of underdetermined linear systems See these old class notes of Marcel Oliver about Gaussian Elimination. See also Hillier/Lieberman Chapter 4.2 (note that the standard form there is slightly different from the one we use in class).
Sep. 14, 2021	Geometry of feasible region and basic solutions
Sep. 16, 2021	Solving a simplex tableau; the simplex algorithm See Section 1 of the notes "Practical Guide to the Simplex Method of Linear Programming" by Marcel Oliver.
Sep. 21, 2021	Solving a simplex tableau; the simplex algorithm (continued) See Section 1 of the notes "Practical Guide to the Simplex Method of Linear Programming" by Marcel Oliver.
Sep. 23, 2021	Introduction to Pyomo Modeling See the pyomo and glpk installation instructions above. The simple program discussed in class (taken from a previous class by Marcel Oliver) can be found here: html, ipynb. See also here for further programs from previous classes.
Sep. 28, 2021	Towards the dual problem; shadow prices Van Roy and Mason, Section 4.1.
Sep. 30, 2021	Sensitivity; weak and strong duality theorems Van Roy and Mason, Sections 4.1 and beginning of 4.2. See also Section 3 of the notes "Practical Guide to the Simplex Method of Linear Programming" by Marcel Oliver for a proof of strong duality. The programs discussed in class (taken from a previous class by Marcel Oliver) can be found here: (1) html, (1) ipynb; and (2) html, (2) ipynb. See also here for further programs from previous classes.
Oct. 05, 2021	Transportation Problems Hillier/Lieberman: parts of Chapter 8.1. The programs discussed in class can be found here: html, ipynb, data file. See also here for further programs from previous classes.
Oct. 07, 2021	Transportation Problems Hillier/Lieberman: parts of Chapter 8.1.
Oct. 12, 2021	Network Optimization: Shortest path, minimum spanning tree Hillier/Lieberman: Chapters 9.1-9.4.
Oct. 14, 2021	Network Optimization: maximum flow problems; minimum cost flow and its linear programming formulation Hillier/Lieberman: Chapters 9.5-9.6.
Oct. 19, 2021	Pyomo implementations of network optimization problems; network duals and their interpretation; arbitrage detection The programs discussed in class can be found here: transportation problem (html), transportation problem (ipynb); shortest path (html), shortest path (ipynb); minimum cost flow (html), minimum cost flow (ipynb); arbitrage detection (html), arbitrage detection (ipynb). See also here for further programs from previous classes.
Oct. 21, 2021	Project management, critical path, project crashing; Review for midterm Hillier/Lieberman: Chapter 9.8. The programs discussed in class can be found here: project management (html), project management (ipynb). See here for practice exams from previous classes.
Oct. 26, 2021	(Mock) Midterm exam See here for the midterm and here for the solutions.
Oct. 28, 2021	Dynamic Programming: Shortest path revisited, "Stagecoach" problem Hillier/Lieberman: Chapters 10.1, 10.2, parts of 10.3
Nov. 02, 2021	Dynamic Programming: Distribution of effort problem, "Local Job Shop" problem Hillier/Lieberman: Chapter 10.3
Nov. 04, 2021	Dynamic Programming and pyomo; probabilistic dynamic programming, "Hit-and-Miss Manufacturing Co." problem Hillier/Lieberman: Chapter 10.4. The programs discussed in class can be found here: local job shop ipopt (html), local job shop ipopt (ipynb). Note: python also has a nice environment for symbolic computations. This can be used to do the computations for the local job shop problem: sympy (html), sympy (ipynb) (this is just for those who are interested, these examples were not discussed in class).
Nov. 09, 2021	Decision analysis: decision trees and the expected value of information, "Goferbroke Oil Co." problem Hillier/Lieberman: Chapter 15.1-15.4.
Nov. 11, 2021	Inventory Theory I: EOQ model (without and with planned shortages) Hillier/Lieberman: Chapter 18.1-18.3.
Nov. 16, 2021	Inventory Theory II: Deterministic periodic review models Hillier/Lieberman: Chapter 18.4.
Nov. 18, 2021	Inventory Theory III: EOQ with stochastic demand, stochastic single-period model for perishable products, "newsvendor problem" Hillier/Lieberman: Chapter 18.7.
Nov. 23, 2021	Nonlinear Programming: Basic examples; nonlinear vs. linear programming; convex optimization Hillier/Lieberman: Chapters 12.1 and 12.2.
Nov. 25, 2021	Special types of nonlinear programs, turning nonlinear programs into linear programs, convexity; using Pyomo to solve nonlinear programs Hillier/Lieberman: Chapter 12.3. See also the other sections of Chapter 12 for more details on some of the disucssed nonlinear programming types. The programs discussed in class can be found here: nonlinear WYNDOR (html), nonlinear WYNDOR (ipynb).
Nov. 30, 2021	Review: Class content
Dec. 02, 2021	Review: Exercises
Dec. 22, 2021	Final exam See here for the final and here for the solutions. See here for the make-up final and here for the solutions.