3+1 Operations Research practical assignment ideas

By Davi Doro — October 27th, 2022

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) — i.e. 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.

Although these ideas can be implemented using any AML, for this tutorial I've chosen to implement the examples in AMPL, which I think is the easiest AML to learn. See languages supported by PIFOP.

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?

Bad solution Good solution

STEP 3: Describe the same problem mathematically, presenting the students to a simple formulation of the problem.

Example:

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:

# Declaration of sets and parameters param n; set V := 1..n; set E dimen 2 = {i in V, j in V : i != j}; param c{(i,j) in E}; # Declaration of variables var x{(i,j) in E} binary; var u{i in V : i >= 2} integer >= 1, <= n-1; # Model minimize z : sum{(i,j) in E} c[i,j] * x[i,j]; subject to c2{i in V} : sum{(i,j) in E} x[i,j] = 1; c3{j in V} : sum{(i,j) in E} x[i,j] = 1; c4{(i,j) in E: i >= 2 and j >= 2}: u[i]-u[j] + (n-1)*x[i,j] <= n-2; Open on PIFOP

STEP 5: Repeat the first 3 steps with another problem, but this time let the students translate the formulation by themselves (or in groups).

Here is a basic AMPL guide that can help your students to complete the assignment.

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 example

Job shop solution example

STEP 3: Present two mathematical formulations of the problem.

Example:

STEP 4: Ask the students to implement both models and solve some small instances of the problem.

Implementation example:

#--------------------------------------- # Manne (1960) #--------------------------------------- param n_jobs, integer, > 0; param n_operations, integer, > 0; param n_machines, integer, > 0; set N; # operations set M; # machines set J := 1..n_jobs; # jobs set job_operations{J}; # job operations set operations_at{M}; # machine operations set A, dimen 2; # operations sequence set E, dimen 2; # each pair is a possible operation # sequence in a machine param p{N}, >= 0; # operation processing time param m{N}, integer, > 0; # machine of each operation param n{M}, integer, > 0; # number of operations in a machine param inf; # "infinity" # Model #------- var t{N}, >= 0; var y{E}, binary; var c_max, >= 0; minimize objective: c_max; subject to c2{(i, j) in A}: t[j] - t[i] >= p[i]; c3{(i, j) in E}: t[j] >= t[i] + p[i] - inf*(1 - y[i,j]); c4{(i, j) in E}: y[i,j] + y[j,i] = 1; c5{i in N}: c_max >= t[i] + p[i]; #---------------------------------------- # Wagner (1959) #---------------------------------------- param n_jobs, integer, > 0; param n_operations, integer, > 0; param n_machines, integer, > 0; set N; # operations set M; # machines set J := 1..n_jobs; # jobs set job_operations{J}; # job operations set operations_at{M}; # machine operations set A, dimen 2; # operations sequence set E, dimen 2; # each pair is a possible operation # sequence in a machine param p{N}, >= 0; # operation processing time param m{N}, integer, > 0; # machine of each operation param n{M}, integer, > 0; # number of operations in a machine param inf; # "infinity" # Model #------- var y{i in N, 1..n[m[i]]}, binary; var t{k in M, 1..n[k]}, >= 0; var s{k in M, 1..n[k]}, >= 0; var s0{k in M}, >= 0; var T{k in M, 1..n[k]}, >= 0; var c_max, >= 0; minimize objective: c_max; subject to c2{k in M, l in 1..n[k]}: sum{i in operations_at[k]} y[i, l] = 1; c3{i in N}: sum{l in 1..n[m[i]]} y[i, l] = 1; c4{k in M, l in 1..n[k]}: T[k, l] = sum{i in operations_at[k]} p[i] * y[i, l]; c5{(i, j) in A, li in 1..n[m[i]], lj in 1..n[m[j]]}: t[m[i], li] + p[i] * y[i, li] - t[m[j], lj] + inf*y[i, li] + inf*y[j, lj] <= inf*2; c6{k in M}: t[k, 1] - s0[k] = 0; c7{k in M, r in 2..n[k]}: s0[k] - t[k, r] + sum{l in 1..(r-1)} (T[k, l] + s[k, l]) = 0; c8{k in M}: c_max >= t[k, n[k]] + T[k, n[k]];
Open on PIFOP

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.

A great place where you can find well-defined real-life optimization problems is the open access journal INFORMS Transactions on Education. They have dozens of case articles showing different real problems being successfully used in operations research courses.

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:

STEP 4: Ask the students to implement the mathematical model adapted to solve the problem of the case.

Implementation example:

# Model #------- set V; param n = card(V); set E dimen 2 = {i in V, j in V : i != j}; param c{(i,j) in E} default 0; var x{(i,j) in E} binary; var y{(i,j) in E} >= 0; var pos{i in V} = n - sum{(i,j) in E} y[i,j] - 1; minimize z : sum{(i,j) in E} c[i,j] * x[i,j]; subject to c2{i in V} : sum{(i,j) in E} x[i,j] = 1; c3{j in V} : sum{(i,j) in E} x[i,j] = 1; c4{(i,j) in E} : (n-1)*x[i,j] >= y[i,j]; c5 : sum{(j,1) in E} y[j,1] + n = sum{(1,j) in E} y[1,j] + 1; c6{(i,j) in E : i != 1} : sum{(jj,i) in E} y[jj,i] = sum{(i,jj) in E} y[i,jj] + 1; # Data #------ set V = 1 "red" "green" "blue" "yellow" "black" "orange" "violet" "brown" "blue-violet" "pink" "white" "yellow-orange" "yellow-green" "blue-green" "red-violet" "red-orange"; param c: 1 "red" "green" "blue" "yellow" "black" "orange" "violet" "brown" "blue-violet" "pink" "white" "yellow-orange" "yellow-green" "blue-green" "red-violet" "red-orange" = 1 . . . . . . . . . . . . . . . . . "red" . . 90 90 180 90 90 90 60 90 165 180 120 180 90 60 45 "green" . 60 . 60 150 90 105 75 105 60 90 180 120 45 30 105 80 "blue" . 90 45 . 120 60 105 30 90 90 90 180 105 90 60 60 90 "yellow" . 60 60 60 . 60 90 75 60 45 60 150 30 15 30 75 75 "black" . 140 120 120 210 . 120 75 120 120 180 240 180 180 120 90 120 "orange" . 150 90 90 115 30 . 90 30 90 90 180 150 120 90 90 30 "violet" . 120 120 90 210 30 105 . 60 30 120 210 210 210 120 75 120 "brown" . 120 105 90 180 30 150 105 . 90 105 180 180 180 90 110 120 "blue-violet" . 120 90 60 150 30 105 90 60 . 120 180 120 120 90 75 105 "pink" . 60 120 120 120 60 90 60 60 60 . 180 120 120 90 60 90 "white" . 30 60 60 15 30 30 30 30 30 30 . 30 30 30 30 30 "yellow-orange" . 90 90 120 120 30 30 30 30 30 60 180 . 90 60 90 30 "yellow-green" . 90 75 60 105 75 90 75 15 60 75 90 120 . 45 90 75 "blue-green" . 90 30 90 120 90 105 45 90 30 90 180 105 120 . 90 90 "red-violet" . 45 60 90 180 45 90 75 45 60 120 180 150 180 105 . 60 "red-orange" . 60 75 90 120 45 120 90 45 90 120 180 60 150 90 75 . ;
Open on PIFOP We don't need to use the time the machine takes to produce each batch in the formulation because, whatever it is, it has a fixed impact on the total time required to produce all colors. Since we can't change the amount of crayons produced for each color, the only way we can make the production faster is by minimizing the total cleaning time.

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.

Visit Working with Google Sheets to learn how to read/write xlsx and csv files using different AMLs. Google Sheets integration

Example: Checkout 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.

When you have sheets in your Google Sheet that are to be read/written to by your mathematical program exclusively, such as the TimeMatrix.csv and Result.csv of this example, consider hiding them, so that you only and your collaborators only see the sheets that are supposed to be manipulated and/or visualized.

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

Terms and Privacy Help Pricing About Blog Contact us Server Status Twitter