Optimization Modeling — E01

Photo by Robin Sommer on Unsplash

What is optimization modeling?

An optimization problem is any problem that can be thought of as a question like “What is the best … ?” For example,

• What is the best route to get from home to work?
• What is the best way to ensure I fulfill my daily diet requirements while remaining under a certain budget?
• What is the best combination of offers I should hand out to maximize profit?

The art and science of formulating questions like the one above into equations and then finding solutions to those equations(and thereby the problem itself) using mathematical techniques is known as Optimization modeling.

What is Operations Research(OR)?

Operations research aims to provide a framework to model complex decision-making in engineering, business, and analytics. OR is essentially using mathematical and quantitative techniques to substantiate the decision being taken.

Optimization is one of the tools used in OR — like simulation, queuing theory, Markov decision processes, etc. We will only be covering optimization is this six-part series.

Introduction to optimization and OR-Tools

Google’s OR-Tools

OR-Tools is an open-source software that solves optimization problems. It is well-structured and has a consistent API for ease of use. While it is written in C++, it has Python and Java wrappers available, hence coding the model becomes extremely easy. It allows one to enjoy the versatility and integration benefits of a general-purpose programming language.

Four-step Optimization Process

A generic framework for solving any optimization problem can be laid down in four steps.

1. Identify the question — zeroing in on the decision variables
2. Identify requirements — translating them into constraints
3. Identify the objective to optimize
4. Solve the model

In order to understand the framework in detail, let’s get started with an actual problem.

Hello, (optimized) world!

Imagine that you manage the kitchen of a food delivery app — Twiggy.

• You have three raw materials(Chicken, Veggies and Spices) available in certain quantities.

• There are three different food categories you can manufacture using these raw materials — Biryani, Bowls and wraps. Each of these requires different units of raw materials — for e.g. Biryani requires 2 units of chicken, 1 unit of veggies and 1 unit of spices
• As the kitchen manager, you want to understand what’s the maximum food packets can you manufacture in each category(upto a maximum of 1000 units in each category) — given the limitation of raw material availability.

Solution Design

Let’s use the four-step process outlined in the earlier sections to design and solve the “kitchen manager” problem.

1. Identify the question — zeroing in on the decision variables
   In this case, we want to find the number of items in each food category. Hence, for three categories, let’s select X0, X1 and X2 to be the three decision variables denoting the number of items in each food category — X0 is #Biryani, X1 is #bowls and X2 is #wraps.
   
   Note: Decision variables are the ones we need to take a decision on — what we’re optimizing for.
2. Identify requirements — translating them into constraints
   There are two different requirements for this problem. One is on the number of items in each category(1000). The other(s) is on the units of raw material available — we could model both of these in the following manner.
   
   0 < X0 ≤ 1000 #Biryani items
   0 < X1 ≤ 1000 #Bowl items
   0 < X2 ≤ 1000 #Wrap items
   
   The constraints on raw materials can be mathematically written as -
   
   2 X0 + X1 + X2 ≤ 1500 #Constraint on chicken raw material
   1 X0 + 3 X1 + 2 X2 ≤ 3000 #Constraint on veggies raw material
   1 X0 + 2 X1 + 3 X2 ≤ 5000 #Constraint on spices raw material
3. Identify the objective to optimize
   The objective, in this case, is simple. We need to maximize X0 + X1 + X2 i.e. the total number of food items in all three categories.
   
   Maximize(X0 + X1 + X2)
4. Solve the model
   Yaay!! We have the model in place. Post this, all we need to do is to solve using any of the various solvers in OR-Tools. Let’s dive into a bit of code to see this in action.

Code

Here’s a snapshot of the code — commented appropriately on the same lines as the four-step solution.

Code for optimization

Code available as a gist here and Jupyter notebook here.

Note: Code embedding is not working on Medium as of now, hence I’ve added an image for reference and provided GitHub links to the actual code.

That completes the first post of this series. I hope that the explanation with the code above was lucid and easy to follow. Please do let me know your thoughts, questions or suggestions in the comment section below.

Topics Overview

This is the first post in the Optimization Modeling series. In the next few posts, we will be covering the following topics around optimization.

1. Introduction to optimization modeling(this post)
   - What is optimization/OR?
   - Solution Design and approach
   - Introduction to OR-Tools(with examples)
2. Continuous Linear Models
   - Mixing
   - Blending
   - Project Management
   - Multi-Stage Models
   - Approximating non-linear problems into linear models
3. Network Models
   - Max Flow
   - Minimum Cost Flow
   - Transshipment
   - Shortest Path problem
4. Discrete Models
   - Minimum Set Cover
   - Set Packing
   - Bin Packing
   - Travelling Salesman Problem
5. Mixed Models(Models which need both continuous AND Discrete Variables) — also called mixed-integer models
   - Facility Locations
   - Multi-Commodity Problem
   - Staffing
   - Job Shop Scheduling
6. Specific Use Case Models
   - Stock cutting
   - Crew Scheduling
   - Sports rostering