Introduction to Linear Optimization
In commercial settings we face trade offs every day, so the question that naturally arises is how can we be confident that we made the right choice? Instead of relying on heuristics or adhoc 'guess and check' approaches, you may be able to formulate the decision as an optimization problem.
An optimization model has three primary components.
- An objective function
- A set of decision variables
- A set of constraints
The goal of an optimization model is to 'optimize' (maximize/minimize) an objective function by finding the best values for controllable decision variables out of all possible values that could satisfy a given set of constraints.
Many commercial decisions can be formulated based on these 3 components hence optimization models are useful in a wide range of fields from manufacturing and scheduling to marketing, finance and transportation.
Example Use Cases
Here are some simple examples to provide you with an idea of how linear optimization could be relevant to your business.
- Manufacturing: Given four potential new products what is the production schedule that maximizes expected profit subject to labor constraints, material constraints, demand estimates and unit pricing.
- Civil Planning: What is the optimal number and location of fire departments to serve a district. Subject to constraints on target response time, expected demand, community size and cost of development.
- Supply Chain: What are the optimal shipping routes that minimizes expenses subject to constraints on availability, demand, reliability and price.
- Portfolio Allocation: What is the optimal portfolio split to maximize expected return given risk appetitie, exposure to various asset classes and time horizon.
- Marketing: What is the optimal funding allocation across multiple campaign channels. Subject to expenses, forecast exposure, risk, target demographic and time duration
Model Components
For a general user the most challenging part of linear optimization is correctly formulating their model. Let's give some more detail on defining your Objective Function, Decision Variables and Constraints.
Objective Function:
The objective function can be viewed as a mathematical expression including your decision variables that will calculate the output you want to maximize or minimize.
Example:
Lets assume a company sells three products and we want to maximize sales revenue. Product one sells for $2000, product two for $1000 and proudct 3 sells for $5000.
If we define our decision variables as \( x_1 \) , \(x_2\) and \(x_3\) representing the number of product 1, 2 and 3 produced respectively, then our objective function is: Maximize \(2000x_1 + 1000x_2 + 5000x_3 \)
Decision Variables:
The decision variables can be thought of as algebraic representations of things you can control within the problem scope. In the earlier example our decision variables were the number of products produced.
Constraints:
A constraint refers to a restriction on a set of decision variables that must be satisfied. In the above example let's assume the company only has 100 hours of staff time available for production. If product 1, 2 and 3 require 10, 5 and 13 hours of labour respectively we can reflect this using the following constraint: \(10x_1 + 5x_2 + 13x_3 \leq 100 \)
Worked Example
Formulating models can be a surprisingly simple task with disproportionate impact. Lets walk through developing a simple model for a construction company. Subsequently I'll show how it can be solved with a quick web app I put together and point you to some python libraries if you're interested in solving your own models.
Background on the Business Problem
Building Co. have purchased 20 acres of land in coastal New South Wales and are trying to determine which type of homes they should build to maximize gross profit. There are four types of homes they can build (see below table) and Building Co. have decided at least 10 models of each should be constructed. Futhermore at least 40 homes must be one story and at least 50 must have three or more bedrooms.
| Acreage | Stories | Bedrooms | Gross Profit | |
|---|---|---|---|---|
| Coastal Cabin | 0.20 | 1 | 2 | $40,000 |
| Beach Bungalow | 0.27 | 1 | 3 | $50,000 |
| Tranquil Townhouse | 0.22 | 2 | 3 | $60,000 |
| Eastern Estate | 0.35 | 2 | 4 | $80,000 |
Goal: Determine the optimal development plan
Formulating the model:
Start by defining your decision variables. Let \(x_i\) be the number of model \(i\) homes developed by Building Co. Where \(i = 1,2,3,4\) corresponds to Coastal Cabin, Beach Bungalow, Tranquil Townhouse and Eastern Estate models respectively.
From the background we know our objective is to maximize gross profit. So lets formulate this algebraically.
Objective function: Maximise: \[40,000x_1 + 50,000x_2 + 60,000x_3 + 80,000x_4\]
The next step is to specify the constraints. Lets list these in general english then specify the mathematical representation.
- C1: At least 10 of each model must be built
- C2: At least 40 homes must be 1 storey
- C3: At least 50 homes must have 3 or more bedrooms
- C4: The total 20 acres can not be exceeded
- C5: It's implied that the number of each model is a positive integer
Constraints:
- C1: \(x_i \geq 10 \forall i, i = 1,...,4 \)
- C2: \(x_1 + x_2 \geq 40 \)
- C3: \(x_2 + x_3 + x_4 \geq 50 \)
- C4: \(0.20x_1 + 0.27x_2 + 0.22x_3 + 0.35x_4 \leq 20 \)
- C5: \(x \in ℤ^+ \)
Implementation and Solving the Model
Stepping through efficient algorithms to solve your now created model is too extensive a topic for this blog. If you are interested in the theory I recommend Operations Research, Applications and Algorithms by Wayne Winston. From a development perspective two good solutions are Gurobi and PuLP. I prefer PuLP given it is free.
coin-orSolution:
Optimal value: $4,610,000
\(x_1 = 29\), \(x_2 = 11\), \(x_3 = 35\), \(x_4 = 10\)
Interpretation of Solution:
Building Co. should develop 29 Coastal Cabins, 11 Beach Bungalows, 35 Tranquil Townhouses and 10 Eastern Estates. This will maximize gross profit subject to the constraints at $4.61m
Solution walkthrough
If you're looking to use linear optimization more in your organization, I recommend having your Data Science team build a simple GUI. This enables all members of the company to harness the results without the need to code.
Below is a demonstration of solving our example problem with a simple web app I put together.
Summary
In this post we went through the core components of translating business problems that require tradeoffs into linear optimization models. These components are the Objective Function, Decision Variables and Constraints.
We then solved a simple example problem and recommended tools to assist in integrating linear optimization into your organization.
Continue the discussion
Feel free to send me an email!
📧 will@willbosler.com