Course number: CO-583-A
Jacobs University, Fall 2022
First class session: Sep. 1, 2022; last class session: Dec. 6, 2022.
All the most recent information about class can be found on this website.
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.
Most of the class material is similar to the following textbook:
A good textbook on Pyomo is:
The assessment for this class is the final exam only. There is a possibility to get bonus points, see below.
There will be a final exam, which is scheduled centrally in the exam period (Dec. 12 - 22, 2022). As practice and to obtain bonus points, there will also be a midterm exam (see class schedule below). Bonus points from the midterm can be obtained from the following table:
| Midterm Points | Bonus |
|---|---|
| 80 or more | 5% |
| 60 - 79 | 4% |
| 40 - 59 | 3% |
| 20 - 39 | 2% |
| 1 - 19 | 1% |
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
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 for each the midterm and the total homework score, and divide by 20, then round. 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: A Student had 80% on the midterm, and a homework average of 50%. The bonus for the midterm is 4%, and the bonus for the homework is 3%. If the final exam score is 70%, then the total grade is 77%.
| Date | Sheet Number | Due Date |
|---|---|---|
| Sep 06, 2022 | Sheet 1 | Sep 14, 2022 |
| Sep 13, 2022 | Sheet 2 | Sep 21, 2022 |
| Sep 20, 2022 | Sheet 3 | Sep 28, 2022 |
| Sep 27, 2022 | Sheet 4 | Oct 05, 2022 |
| Oct 04, 2022 | Sheet 5 | Oct 12, 2022 |
| Oct 11, 2022 | Sheet 6 | Oct 19, 2022 |
| Oct 18, 2022 | Sheet 7 | Oct 26, 2022 |
| Oct 25, 2022 | Sheet 8 | Nov 09, 2022 |
| Nov 08, 2022 | Sheet 9 | Nov 16, 2022 |
| Nov 15, 2022 | Sheet 10 | Nov 23, 2022 |
| Nov 22, 2022 | Sheet 11 | Nov 30, 2022 |
| Nov 29, 2022 | Sheet 12 | Dec 07, 2022 |
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
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. 01, 2022 | 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. 06, 2022 | Linear Programming: Graphical Solution See R. Larson, Elementary Linear Algebra, Chapter 9.2; also: Hillier/Lieberman Chapter 3.2 |
| Sep. 08, 2022 | Graphical Solution continued; Standard form of an LP problem, See references from last session, plus Hillier/Lieberman Chapter 4.2 (note that the standard form there is slightly different from the one we use in class). See Resources for more on matrix multiplication. |
| Sep. 13, 2022 | Slack variables (standard form of LP problems), short review of underdetermined linear systems (augmented matrix, row echelon form) See these old class notes of Marcel Oliver about Gaussian Elimination. See also Hillier/Lieberman Chapter 4.2 (Note: The book uses the maximization convention for the standard form.) |
| Sep. 15, 2022 | Review of underdetermined linear systems, basic solutions See references of previous session. |
| Sep. 20, 2022 | Geometry of feasible region and basic solutions Hillier/Lieberman Chapters 4.1 and 4.2. |
| Sep. 22, 2022 | 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. Note: The Hillier/Lieberman book can also be consulted: see Chapters 4.2-4.4; however, the convention and notation used there is slightly different from the one we use in class. |
| Sep. 27, 2022 | Solving a simplex tableau; the simplex algorithm References as in previous session. |
| Sep. 29, 2022 | 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. |
| Oct. 04, 2022 | Towards the dual problem Van Roy and Mason, beginning of Section 4.1. |
| Oct. 06, 2022 | Shadow prices; 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: How to use indexed decision variables: (1) html, (1) ipynb; How to get the dual variables (shadow prices) and solve the dual problem: (2) html, (2) ipynb. |
| Oct. 11, 2022 | Transportation Problems Hillier/Lieberman: parts of Chapter 8.1. The programs discussed in class can be found here: html, ipynb, data file. |
| Oct. 13, 2022 | Transportation Problems Hillier/Lieberman: parts of Chapter 8.1. |
| Oct. 18, 2022 | Network Optimization: Shortest path problems Hillier/Lieberman: Chapters 9.1-9.3. |
| Oct. 20, 2022 | Dual variables and transportation problems in pyomo; shortest path problem continued, minimum spanning tree problems Hillier/Lieberman: Chapters 9.3 and 9.4. The programs discussed in class can be found here: Dual variables in the Wyndor problem: html, ipynb; Dual variables and dummy sources in transportation problems (Problem 2 from Homework Sheet 6): html, ipynb. |
| Oct. 25, 2022 | Network Optimization: maximum flow problems; minimum cost flow Hillier/Lieberman: Chapters 9.5 and 9.6. |
| Oct. 27, 2022 | Minimum cost flow and its linear programming formulation; Pyomo implementations of network optimization problems; network duals and their interpretation; (extra material: Project management, critical path, project crashing) Hillier/Lieberman: Chapter 9.6 (and 9.8 for the extra material). The programs discussed in class can be found here: shortest path (html), shortest path (ipynb); minimum cost flow (html), minimum cost flow (ipynb). See also here for a pyomo implementation of the PT company problem: transportation problem PT company (html), transportation problem PT company (ipynb). Pyomo programs about the extra material: project management (html), project management (ipynb). |
| Nov. 01, 2022 | (Mock) Midterm exam See here for the midterm and here for the solutions. See here for the make-up midterm and here for the solutions. |
| Nov. 03, 2022 | Dynamic Programming: Shortest path revisited, "Stagecoach" problem Hillier/Lieberman: Chapters 10.1 and 10.2 |
| Nov. 08, 2022 | Dynamic Programming: Distribution of effort problem, "Local Job Shop" problem Hillier/Lieberman: Chapter 10.3 |
| Nov. 10, 2022 | 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. 15, 2022 | Decision analysis: decision trees and the expected value of information, "Goferbroke Oil Co." problem Hillier/Lieberman: Chapters 15.1-15.4. |
| Nov. 17, 2022 | Decision analysis continued; Inventory Theory I: EOQ model (without planned shortages) Hillier/Lieberman: Chapter 18.1-18.3. |
| Nov. 22, 2022 | Inventory Theory II: EOQ model with planned shortages Hillier/Lieberman: Chapter 18.3. |
| Nov. 24, 2022 | Inventory Theory III: deterministic periodic review models Hillier/Lieberman: Chapter 18.4. |
| Nov. 29, 2022 | Inventory Theory IV: EOQ with stochastic demand, stochastic single-period model for perishable products, "newsvendor problem" |
| Dec. 01, 2022 | Nonlinear Programming: Basic examples; nonlinear vs. linear programming; convex optimization; using Pyomo to solve nonlinear programs Hillier/Lieberman: Chapters 12.1 and 12.2. 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). |
| Dec. 06, 2022 | No class, but take a look at the review notes. |
| Dec. 20, 2022 | Final exam See here for the final and here for the solutions. |
| Jan. 30, 2023 | Final exam (make-up) See here for the make-up final and here for the solutions. |