Teaching Operations Research — A “Code First” Approach
Initial technical topics of optimization regarding Operations Research (OR), such as Linear Programming (LP) and Mixed Integer Linear Programming (MILP), are in the category of “easy to learn, hard to master” skills, in my opinion. Therefore, teaching the ropes before the theory always made sense.
However “ropes” is a two stage term. First stage is to formulate the mathematical model and the second stage is to solve it. In this post, I will discuss the essential parts of optimization and propose a skeleton of a short syllabus. The objective function is to minimize “time to fundamental skills acquisition”.
I’m writing this post to gather my thoughts to build a short “Introduction to OR” course for my lecture. So, your input is most welcome.
Diet Problem Example
“Diet problem” is one of the introductory examples of Linear Programming. Briefly you are expected to create a “menu” consisting of different food combinations. Each food item has a nutrition content (e.g., energy kcal, fat %, protein etc.) . You need to stay within nutrition guidelines (i.e., minimum and maximum amounts for each nutrition type) and minimize the total cost of the meal.
You can find the problem formulation and codes in Julia’s JuMP documentation. It is also the perfect illustration of the point I would like to make. The tutorial explains the problem, performs the algebraic formulation of the mathematical model and provides the code.
“Back in My Day”
It has been more than 17 years since I got my first class in Operations Research (special thanks to my professors at METU). Given the history of OR, I admit that my personal history is quite short. Even so, methodology of developing OR-based software changed a lot since then. I remember that an older alumni came to a panel to talk about how they performed simplex on really long sheets of paper, by hand 😱, back in their day.
Thankfully, we started with Excel solver add-in. Then, we are introduced to LINDO and LINGO. Finally, we were modelling in GAMS and solving in CPLEX (no Gurobi back then, I hazard diverging from the topic by adding this link). We also had excellent lectures on theory (but my head is a bit thick, so only a little passed through): Duality, simplex, branch-and-bound (and perhaps branch-and-cut? also not so sure about interior point methods) and some heuristics we also covered the math at the undergrad level. We had three semesters of Operations Research (I, II & III) courses with other mathematical modelling courses on supply chain, scheduling etc. I feel really, really lucky about it.
So, what is wrong?
However, what we were lacking is the proper tools to connect what we learned in theory to applications. We required very specific software to perform optimization. Not everywhere had GAMS and CPLEX, nor were they inclined to buy a license.
Industrial Engineering (IE) wasn’t exactly a CS department. Sure there were coding classes (C, C++, SQL etc.) but follow-up was limited. For OR specific tasks we relied on GAMS+CPLEX. Also I shall admit that open source scripting languages such as Python and R weren’t as popular as today. Julia didn’t exist at all.
Today is different.
Language of choice
Today we can choose from a variety of Algebraic Modelling Languages (AMLs). Here is a short list for scripting programming languages.
Python: PuLP, Pyomo
R: ompr
Julia: JuMP
This list is not exhaustive but first on top of my mind. There are other excellent AMLs for various needs. There are also AMLs for specific solvers (e.g., gurobipy). However I have several criteria for the AML of choice:
- It should be part of an ecosystem: Direct library installations just cuts the middlemen. So packages
- It should be open source and free: It eliminates lovely AMLs such as GAMS and AMPL (even though they have free versions).
- License should be permissive: MIT is excellent, GPL 2.0 is acceptable.
- It should connect to a large collection of solvers in a standardized way.
Solver of Choice
This part is a bit more complicated. Mainly because, many high performing solvers are commercial but available for free for education. Some solvers are free to use and open source, but they do not allow commercial use without license (e.g. SCIP). Also, different solvers are good for different tasks.
So we are looking for a solver which is quite good in LP and MILP problems, open source and has a permissive license. Lucky for us, there now is such solver: HiGHS.
HiGHS is gaining traction in both academia and industry. It performs quite well according to Mittlemann Benchmarks (best open source). It is MIT licensed so you can use it in commercial applications. It has integrations with R, Python and Julia packages. It is supported. I think HiGHS is the beginning of a new era of Torch-ing or Tensorflow-ing of OR models.
(Update: A few weeks after writing the draft of this post, SCIP announced that their license will now be a permissive Apache License 2.0)
Syllabus
Now that we have all the information let’s build a short syllabus.
- Introduction to LP modelling. Start with a simple example problem (e.g., diet problem).
- Step-by-step, build the mathematical model and introduce concepts (i.e. decision variable, constraint, objective function etc.)
- Transfer mathematical model to code using a programming/scripting language, algebraic modelling language and solver of choice. For example, Julia-JuMP-HiGHS.
- Give tons of exercises and problems for the students to model. Make them code at least a few of them.
- Introduce integer and binary decision variables. Enter MILP.
- Again tons of exercises.
- Explain about AML, solvers and the expanded ecosystem (e.g., MINLP, CP, SCP etc.). Tell there are better solvers which might be commercial such as Gurobi, CPLEX, XPress, COPT etc. Tell them there are very good solvers for other problem types such as Knitro, Octeract, OR-Tools etc. Tell them about Mittelmann Benchmarks. Let them dig around a bit.
- Optionally have them solve the same problems with comercial GAMS/AMPL and Gurobi/CPLEX.
- Give the theory. Duality, Simplex, Branch-and-Bound, KKT, heuristics etc.
The controversial part here is pushing the theory to the end. Any respectable academic institution worth their name would (and should) prioritize theory over practice at their undergraduate and academic graduate programs. Despite the fact that I’m dealing with practice more than theory does not mean that I forsake the merits of theoretical foundations.
On the contrary, I highly suggest a deep theoretical instruction for such programs by keeping the “sweet” part brief and letting students figure out the practice part. For other cases such as grad programs and trainings aimed at professionals, let them gain full intuition on the application and then sprinkle the theory. Then, let them decide if they want to go deeper.
Conclusion
Let’s wrap it up. This post is about building the next level “Introduction to OR” education methodology. We switch from classical solutions which are not freely applicable, to open source permissive solutions and widely used programming languages.
We push the theory to the end and put coding right after modelling. We want them to get the intuition of modelling.
We provide an expanded view of the OR universe as early as possible. We explain them the tools and their general use cases. We provide sources for them to explore at their own time.
If the course is academically inclined we weigh on theory, if professionally inclined we weigh on application. Never ever forget about the merits of theoretical foundations.
Finally, OR is a really good topic for today’s needs with great prospects. The more people knowing about OR is always the better.
