3+1 Operations Research practical assignment ideas
Operations research is applied math, so it is a must that we teach our students how to apply the linear, integer and other mathematical programming techniques to solve problems.
I believe that the best way to do that is to engage our students into model implementation practical assignments using an algebraic modeling language (AML) — e.g. AMPL, GAMS and OPL. Here are some ideas with different levels of difficulty for you to try out. The last one is an extra tip on how your students can take their mathematical programs to the next level by integrating them with Google Sheets.
- Idea #1: Translate model to an AML (easy)
- Idea #2: Compare two formulations of the same classic problem (medium)
- Idea #3: Solve a well defined real-world problem (advanced)
- EXTRA: Use Google Sheets for input and output processing (advanced)
Idea #1: Translate model to an AML (easy)
Teaching objectives: Get the students familiar with the basic model entities and statements of the language. Show the correspondency between the entities and statements of the language and the algebraic notation using traditional math symbols.
STEP 1: Choose a simple classic optimization problem.
Examples: TSP, VRP or Bin packing. For the next steps, I will be using the TSP as an example.
STEP 2: Describe the problem to your students using layman's terms.
Example: I'm a trucker that works for a transportation company that makes deliveries for Amazon. I just picked up the products that I should deliver today. I have to finish the deliveries in the shortest time possible — without exceeding speed limits, of course ;-) In which order should I make the deliveries?
STEP 3: Describe the same problem mathematically, presenting the students to a simple formulation of the problem.
Example:
#### Data — things I know beforehand
- `$V$` — set of delivery stops (including the depot) `$i \in V$`
- `$n = |V|$` — total number of stops
- `$i = 1$` — Amazon depot
- `$E$` — set of direct paths `$(i,j)$`, such that `$i \in V$` and `$j \in V$`
- `$c_{ij}$` — length of path `$(i,j)$`
- **Note:** `$c_{ij}$` may or may not be equal to `$c_{ji}$`
#### Model — MTZ (1960)
- ```LATEX
x_{ij}=
\begin{cases}
1 & \text{if I should go from $i$ to $j$ directly} \\
0 & \text{otherwise}
\end{cases}
```
- `$u_i \in \Z$` `$\forall i \in 2...n$` — auxiliary variables that keeps track of the order in which the stops are visited:
`$u_i \le u_j$` means that `$i$` is visited before `$j$`.
```LATEX
\begin{array}{lrcllr}
\text{minimize } & z & = & \displaystyle \sum_{(i,j) \in E} c_{ij}x_{ij} & & (1) \\
\text{subject to} & \displaystyle \sum_{(i,j) \in E} x_{ij} & = & 1 & \forall i \in V & (2) \\
& \displaystyle \sum_{(i,j) \in E} x_{ij} & = & 1 & \forall j \in V & (3) \\
& u_i - u_j + (n-1) x_{ij} & \le & n-2 & \forall 2 \le i \ne j \le n & (4) \\
& 1 \le u_i & \le & n-1 & \forall 2 \le i \le n & (5) \\
\end{array}
```
STEP 4: Translate the formulation to an AML with your students. Ask them to implement the program along with you so that they start to get used to the AML's syntax and program structure.
Example:
STEP 5: Repeat the first 3 steps with another problem, but this time let the students translate the formulation by themselves (or in groups).
Idea #2. Compare two formulations of the same classic problem (medium)
Teaching objectives: Teach the students that the same problem can be formulated in different ways. Teach the different aspects in which we can compare two formulations, e.g. the number of constraints and variables, the linear relaxation gap, the solver time performance when using a given model to solve medium size instances, etc. Teach how to use the AML to retrieve these pieces of information.
STEP 1: Choose a simple classic optimization problem.
Examples: TSP, VRP or Bin packing. For the next steps, I will be using the job shop scheduling problem as an example.
STEP 2: Explain the problem to your students.
Example: I'm the manager of a woodshop. We make all kinds of wood furniture: chairs, tables, shelfs, etc. The making of a given furniture may require the use of various machines and professionals in a specific order: cutter, folder, painter, etc. We have a good estimate of how much time it takes to complete each processing stage of each type of furniture.
Given a list of products that we have to deliver to a customer, how should I schedule the use of the machinery and professionals in order to complete the whole list as soon as we can?
Job shop solution example
STEP 3: Present two mathematical formulations of the problem.
Example:
#### Data
- `$N$` — set of operations
- `$p$` — processing time of operation `$i$`
- `$M$` — set of machines/professionals
- `$A = \{(i,j) : i \in N, j \in N, i \ne j, i \prec j\}$` — set of operation pairs that represent the
order in which they should occur.
- `$m_i$` — machine required by operation i
- `$E = \{(i,j) : i \in N, j \in N, i \ne j, m_i = m_j\}$` — set of operation pairs where each pair
represents a possible precedence of operation i to operation j, given that i and require the
same machine.
- **M** — big positive value.
- `$n_k$` — number of operations executed in machine `$m_k$`.
#### 1. Manne's model (1960)
- `$t_i$` — start date of operation i
- ```LATEX
y_{ij} =
\begin{cases}
1 & \text{if $i$ preceeds $j$ in $m_i$ ($= m_k$)} \\
0 & \text{otherwise}
\end{cases}
```
```LATEX
\begin{array}{lrcllr}
\text{minimize } & C_{max} & & & & (1.1) \\
\text{subject to} & \displaystyle t_j - t_i & \ge & p_i & \forall (i,j) \in A & (1.2) \\
& \displaystyle t_j & \ge & t_i + p_i - M(1-y_{ij}) & \forall (i,j) \in E & (1.3) \\
& \displaystyle y_{ij} + y_{ji} & = & 1 & \forall {(i,j) ; (j,i)} \subset E & (1.4) \\
& \displaystyle C_{max} & \ge & \displaystyle t_i + p_i & \forall i \in N & (1.5) \\
\end{array}
```
#### 2. Wagner's model (1959)
- ```LATEX
y_i^l =
\begin{cases}
1 & \text{if $i$ is the $l^{th}$ operation in machine $m_i$} \\
0 & \text{otherwise}
\end{cases}
```
- `$t_k^l$` — start date of the `$l^{th}$` operation in machine `$m_i$`
- `$s_k^l$` — duration between the end of the `$l^{th}$` operation and the begining
of the `$(l+1)^{th}$` operation in machine `$m_k$` (slack variable)
- `$s_k^0$` — duration between 0 and the first operation in machine `$m_k$`
- `$T_k^l$` — processing time of the `$l^{th}$` operation in machine `$m_k$`
```LATEX
\begin{array}{lrcllr}
\text{minimize } & C_{max} & & & & (2.1) \\
\text{subject to} & \displaystyle \sum_{i \in N : m_i = k} y_i^l & = & 1 & \forall k \in M, l = 1...n_k & (2.2) \\
& \displaystyle \sum_{l = 1}^{n_k} y_i^l & = & 1 & \forall i \in N & (2.3) \\
& \displaystyle T_k^l & = & \displaystyle \sum_{i \in N : m_i = k} p_i y_i^l & \forall k \in M, l = 1...n_k & (2.4) \\
& \displaystyle t_{k_1}^{l_1} + p_i y_i^{l_1} & \le & \displaystyle t_{k_2}^{l_2} + M(2 - y_i^{l_1} - y_j^{l_2}) & \displaystyle \forall
\begin{cases}
(i,j) \in A, \\
l_1 = 1...n_{k_1} \\
l_2 = 1...n_{k_2}
\end{cases} & (2.5) \\
& \displaystyle t_k^1 & = & s_k^0 & \forall k \in M & (2.6) \\
& \displaystyle t_k^r & = & \displaystyle s_k^0 + \sum_{l=1}^{l=r-1} (T_k^l + s_k^l) & \forall k \in M, r = 2...n_k & (2.7) \\
& \displaystyle C_{max} & \ge & t_k^{n_k} + T_k^{n_k} & \forall k \in M & (2.8)
\end{array}
```
STEP 4: Ask the students to implement both models and solve some small instances of the problem.
Implementation example:
STEP 5: Teach the students how to use the AML to get information about the model. Then ask the students to compare both models: which one is larger, in terms of number of constraints? Which is faster? Which gives a better relaxation gap? etc.
Idea #3. Solve a well defined real-world problem (advanced)
Teaching objectives: Show students how linear and integer programming can be used to solve real-world problems. Provide the students hands-on experience in adapting and applying classic optimization problem models to real-life scenarios.
STEP 1: Select or invent a scenario in which linear or integer programmming can be applied to solve a real-life problem.
Example: Let's use an asymmetric TSP model to find the optimal production schedule of a the ficticious DeLand Crayon Company (Rao et al 2020). To keep this example simple, let's focus exclusively on the single machine scheduling problem presented in the article.
In short, this is the problem we want to solve: the DeLand Crayon factory has a single automatic rotary molding machine that is used to produce 16 different colors of crayons. After finishing a batch of a given color, the machine has to be cleaned to start producing a new color, which can take minutes or hours.
Some color changes demand a deeper cleaning, and while going from color A to color B may require X minutes of cleaning that does not necessarily mean that going from B to A will require the same amount of time. For instance, the black paint can darken the white paint much more easily than the white paint can lighten the black paint, so the machine has to be better cleaned when going from Black to White than when going from White to Black.
The batch size of a color — i.e. the amount of crayons that the machine produces when it is being used to produce that color — is equal to its estimated weekly demand. Every week DeLand must produce one batch of each one of the 16 colors. Given the estimated cleaning time for every possible color change (see Appendix B), how should we schedule the production in order to produce one batch of every color as fast as possible?
STEP 2: Solve the problem mannually using an easy to follow heuristic.
This is important so that at the end of the project the students have a baseline to which they compare the optimal solution.
Example: the DeLand scheduling problem can be solved by a greedy heuristic where, starting from white, the next color to be produced is always the color that requires the least amount of cleaning time.
STEP 3: Introduce the students to the classic problem(s) to which the case is related.
For instance, if the case is a transportation problem, it may be helpful for the students to know about TSP and VRP problems.
Example: The single machine scheduling problem described above can be modeled as an asymmetric TSP — ATSP — where the nodes are the crayon colors to be produced and the arcs are the cleaning times.
The ATSP can be modeled as such:
#### Data
- `$V$`: set of vertices `$i \in V$`
- `$n = |V|$`: total number of cities in the salesman region
- `$i = 1$`: city where the salesman lives
- `$E$`: set of arcs `$(i,j)$`, such that `$i \in V$` and `$j \in V$`
- `$c_{ij}: (i,j) \in E$`: distance between cities `$i \in V$` and `$j \in V$`; `$c_{ij}$` may or may not be equal to `$c_{ji}$`.
#### Variables
- ```LATEX
x_{ij}=
\begin{cases}
1 & \text{if the salesman travels directly from city $i$ to city $j$} \\
0 & \text{otherwise}
\end{cases}
```
- `$y_{ij} \geq 0$`, for all `$(i,j) \in E$`: number of products the salesman has when going from city `$i$` to city `$j$`.
#### Model
```LATEX
\begin{array}{lrcllr}
\text{minimize } & z & = & \displaystyle \sum_{(i,j) \in E} c_{ij}x_{ij} & & (1) \\
\text{subject to} & \displaystyle \sum_{(i,j) \in E} x_{ij} & = & 1 & \forall i \in V & (2) \\
& \displaystyle \sum_{(i,j) \in E} x_{ij} & = & 1 & \forall j \in V & (3) \\
& \displaystyle (n-1) x_{ij} & \geq & y_{ij} & \forall (i,j) \in E & (4) \\
& \displaystyle \sum_{(j,1) \in E} y_{j1} + n & = & \displaystyle \sum_{(1,j) \in E} y_{1j} + 1 & & (5) \\
& \displaystyle \sum_{(j,i) \in E} y_{ji} & = & \displaystyle \sum_{(i,j) \in E} y_{ij} + 1 & \forall (i,j) \in E \lor i \neq 1 & (6) \\
& \displaystyle x_{ij} & \in & \{0,1\} & \forall (i,j) \in E & (7) \\
& \displaystyle y_{ij} & \geq & 0 & \forall (i,j) \in E & (8) \\
\end{array}
```
STEP 4: Ask the students to implement the mathematical model adapted to solve the problem of the case.
Implementation example:
In this example, there are no adaptations of the ATSP model needed to solve the DeLand scheduling problem. The only thing we've added to the model implementation is a pos defining variable that has no influence on the problem solution. Its only purpose is to hold the position of a color in the schedule sequence, so that we can more easily show it with the statement display pos.
If you are working with a more complex problem, you can break this step into two: first, ask the students to implement the model that solves the classic problem and second, ask them to adapt the model and the implementation to solve the problem in question.
STEP 5: Extend the problem by asking additional questions.
My suggestion is that you ask "what if" to reinforce students' modeling and decision making skills.
Examples:
- What if the factory, instead of operating 24 hours a day, operated 16 hours a day? Would it still be able to meet the weekly demand?
- What if there is a demand spike in a given week that makes the demand of the 5 most popular colors double? Is the factory capable of meeting this demand increase?
EXTRA: Use Google Sheets for input and output processing (advanced)
Teaching objectives: Teach the students the benefits of integrating a mathematical program with spreadsheet software. Show them how to read pre-processed data from Google Sheets. Show them how to generate tables and charts based on the solver output.
STEP 1: Discuss the advantages of integrating a mathematical program with a spreadsheet software.
Data processing and visualization is an important part of optimization problem solving, and it is much easier to manipulate and visualize data using a spreadsheet than using an AML. Here are three reasons why:
- Large data: It is much easier to read and work with large instances when the data is nicely formatted in a spreadsheet than when it is in a text file. Additionally, it is often the case that the input data of large real-world problems is readily available in some kind of spreadsheet format, e.g. xlsx and csv.
- Data pre-processing: More often than not, the input data that defines an instance of a mathematical model has to be derived from one or more sources. For instance, sometimes we need the average of a set of records, or the source data has to be converted to another unit, or scaled, or a data set has to be transposed, etc. These are simple tasks to accomplish using a spreadsheet, but can be very annoying to do using an AMLs.
- Data visualization: Generating tables and charts from the solution returned by the solver can help us to make sense of it and to present and explain it to others. The same can be said about tables and charts of input data, which can help us in the comparison of different scenarios.
STEP 2: Teach the students how to read/write data from/to a spreadsheet.
You can do that as an extension of a previous assignment that the class has already done. Teach them how to make the necessary changes to the program implementation so that the input data is read from a spreadsheet and the output is written to it.
Example: Check out this modified version of the DeLand Crayons example in which we read data from the TimeMatrix.csv sheet and write data to the Result.csv sheet, both of which live in this Google Sheet file.
Notice how I have used Google Sheet to pre-process the data found in the appendix of Rao et al 2020 to arrive at the production time needed to produce the weekly demand of each color.
Notice also how I am arriving at the numbers on the Optimal Schedule sheet by combining the schedule written by the program to Result.csv with the pre-processed data in Colors. This is what allows me to dinamically generate the waterfall chart showing the schedule returned by the solver.
STEP 3: The sky is the limit.
Once the students know how they can read/write data from/to a spreadsheet format, the possibilities in which they can play with input and output data are unlimited. You can ask them to create complex dashboards and to generate all kinds of charts and tables.
Create your own assignments online!
You and your students can create, share and complete modeling assignments online using PIFOP for free! Sign in to get started, or create a free account!
I hope that these tips can help you.
Until next time!
— Davi