Course number: CO-583-A
Constructor University, Fall 2023
First class session: Sep 5, 2023; last class session: Dec 7, 2023.
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, 2023). 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 05, 2023 | Sheet 1 | Sep 13, 2023 |
| Sep 12, 2023 | Sheet 2 | Sep 20, 2023 |
| Sep 19, 2023 | Sheet 3 | Sep 27, 2023 |
| Sep 26, 2023 | Sheet 4 | Oct 04, 2023 |
| Oct 03, 2023 | Sheet 5 | Oct 11, 2023 |
| Oct 10, 2023 | Sheet 6 | Oct 18, 2023 |
| Oct 17, 2023 | Sheet 7 | Oct 25, 2023 |
| Oct 24, 2023 | Sheet 8 | Nov 01, 2023 |
| Nov 07, 2023 | Sheet 9 | Nov 15, 2023 |
| Nov 14, 2023 | Sheet 10 | Nov 22, 2023 |
| Nov 21, 2023 | Sheet 11 | Nov 29, 2023 |
| Nov 28, 2023 | Sheet 12 | Dec 06, 2023 |
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. 05, 2023 | 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, 2023 | Linear Programming: Graphical Solutions See R. Larson, Elementary Linear Algebra, Chapter 9.2; also: Hillier/Lieberman Chapter 3.2 |
| Sep. 12, 2023 | Standard form of an LP problem 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. 14, 2023 | Short review of underdetermined linear systems (augmented matrix, row echelon form), basic solutions 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. 19, 2023 | Geometry of feasible region and basic solutions Hillier/Lieberman Chapters 4.1 and 4.2. |
| Sep. 21, 2023 | 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. 26, 2023 | The simplex algorithm; Introduction to Pyomo Modeling See references from previous session for the simplex algorithm. For pyomo: 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, 2023 | Towards the dual problem; Introduction to Pyomo Modeling Van Roy and Mason, beginning of Section 4.1. For pyomo: See the pyomo and glpk installation instructions above. |
| Oct. 03, 2023 | No class (German Unity Day) |
| Oct. 05, 2023 | 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. 10, 2023 | Transportation Problems Hillier/Lieberman: parts of Chapter 8.1. The programs discussed in class can be found here: html, ipynb, data file. |
| Oct. 12, 2023 | Transportation Problems Hillier/Lieberman: parts of Chapter 8.1. |
| Oct. 17, 2023 | Network Optimization: Shortest path problems Hillier/Lieberman: Chapters 9.1-9.3. |
| Oct. 19, 2023 | Dual variables and transportation problems in pyomo; minimum spanning tree problems, maximum flow problems Hillier/Lieberman: Chapters 9.4 and 9.5. The programs discussed in class can be found here: Dual variables and dummy sources in transportation problems (Problem 2 from Homework Sheet 6): html, ipynb. |
| Oct. 24, 2023 | Network Optimization: minimum cost flow Hillier/Lieberman: Chapter 9.6. |
| Oct. 26, 2023 | Pyomo implementations of network optimization problems; network duals and their interpretation; Project management (critical path, project crashing) Hillier/Lieberman: Chapters 9.6 and 9.8. 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). Further pyomo programs: project management (html), project management (ipynb); arbitrage detection (html), arbitrage detection (ipynb). |
| Oct. 31, 2023 | No class (Reformation Day) |
| Nov. 02, 2023 | Dynamic Programming: Shortest path revisited, "Stagecoach" problem Hillier/Lieberman: Chapters 10.1 and 10.2 |
| Nov. 07, 2023 | Dynamic Programming: Distribution of effort problem, "Local Job Shop" problem Hillier/Lieberman: Chapter 10.3 |
| Nov. 09, 2023 | Midterm exam (for bonus points) See here for the midterm and here for the solutions. See here for the make-up midterm and here for the solutions. |
| Nov. 14, 2023 | Dynamic Programming; "Local Job Shop" problem; probabilistic dynamic programming, "Hit-and-Miss Manufacturing Co." problem Hillier/Lieberman: Chapter 10.4. As extra material, here is a python program solving the local job shop problem: 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. 16, 2023 | Probabilistic dynamic programming continued; Decision analysis: decision trees and the expected value of information, "Goferbroke Oil Co." problem Hillier/Lieberman: Chapters 15.1-15.4. |
| Nov. 21, 2023 | Decision analysis continued Hillier/Lieberman: Chapters 15.1-15.4. |
| Nov. 23, 2023 | Inventory Theory: EOQ model with and without planned shortages Hillier/Lieberman: Chapters 18.1-18.3. |
| Nov. 28, 2023 | Inventory Theory: deterministic periodic review models Hillier/Lieberman: Chapter 18.4. |
| Nov. 30, 2023 | Inventory Theory: EOQ with stochastic demand (stochastic single-period model for perishable products, "newsvendor problem") Hillier/Lieberman: Chapter 18.7. |
| Dec. 05, 2023 | 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. 07, 2023 | Review |
| Dec. 21, 2023 | Final exam |