Linear programming is an optimization technique used to find the best outcomes for a given problem. This technique relies on a set of constructs which are all expressed using a system of linear equations. It is important to understand that you should be able to express your objective as a linear equation dependent on an arbitrary number of variables. If your objective is non linear (example: quadratic equations – then you can use Quadratic Programming aka QP) then you cannot use linear programming techniques to optimize the outcomes (objectives).
linear programming is mathematical modeling technique in which a linear function is maximized or minimized when subjected to various constraints.
Britannica, The Editors of Encyclopaedia. “linear programming”. Encyclopedia Britannica, 13 Jan. 2023, https://www.britannica.com/science/linear-programming-mathematics. Accessed 24 February 2023.
Let’s Understand the linear programming technique with an easy example, let’s say you are a nutritionist who would like to find the best meal plan for a patient based on a few factors, the patient is suffering from Anemia and you would like to design a meal plan for the patient to find the best meals for the patient from the hospital dialy menu such that they get the maximum possible content of Vitamin B12 subject to a few contraints.
Parameter | Type | Description |
Vitamin B-12 | Objective | Maximize the content of Vitamin B-12 in patient’s meals |
Vitamin B-12 | Constraint | The total Vitamin B-12 content should not be less than 2.4 mg in all meals combined for any given day. |
Number of Meals | Constraint | We have to meet the objective by feeding exactly 3 meals (no less no more) to the patient per day (breakfast, lunch, dinner) |
Calories | Constraint | The total calories content in all meals combined should not be less than 2500 calories (given that our patient is an adult male) |
From the above table we can see that there are a few abstractions/constructs that need to be well defined in relation to an objective and now let’s understand what each of these are.
Important Concepts
Term | Meaning |
Objective | Objective is the goal that you are trying to optimize, in above example the objective that we are trying to optimize is the Vitamin B-12 content in the meals. You can either Maximize or Minimize a given objective. It is also possible to optimize multiple objectives using linear programming and we will cover that in the upcoming posts in this series. |
Constraint | A constraint is a condition that you would like to fulfill while optimizing the objective. In our example we defined a few constraints like the minimum limit for Vitamin B-12 content (2.5 mg), The exact number of meals and the lower threshold of calories intake per day |
Learn With A Practical Example
Most readers visit my blog for easy to follow guides around complicated topics and this one is no exception, so we will start with a very simple and intuitive example problem.
The Diet Problem
Design a lowest cost diet that provides sufficient protein, with
two choices:
- steak: 2 units of protein/pound, $x/pound
- peanut butter: 1 unit of protein/pound, $y/pound
Proper diet needs 4 units protein/day.
โLinear Programming: The Ultimate Practical ProblemโSolving Model.โ Oregon State University, Oregon State University, https://web.engr.oregonstate.edu/~xfern/classes/cs325/lectures/lp.pdf.
The above is a simple problem with a goal that can be expressed as a linear equation between 2 variables. So let’s breakdown the variables and understand the constraints as well.
Variables
In our example we have 2 variables, quantity of steak and peanut butter. we can denote them with whatever name we want but for this guide we will be denoting them with S and P respectively.
- Let S be the number of pounds of steak per day.
- Let P be the number of pounds of peanut butter per day.
Goal
Our goal is to minimize the cost of meals per day while meeting the requirements of serving atleast 4 units of proteins per day. The cost of both inputs (steak and peanut butter) can fluctuate per day and our goal is to create a model that can determine the best combination of steak and peanut butter with minimum cost to meet the constraints (discussed in next section). Let’s assume that for a given day price per pound of steak is 3 currency units (it could be dollars or euros or any other currency for that matter) and price per pound of peanut butter is 2 currency units. So our goal is to:
The above goal formulation might look a bit terse on mathematical notation `but we will break it down below.
- Cost: Cost of daily meals is given by the price per pound of inputs (steak and peanut butter) times the pounds of inputs (steak and peanut butter)
- Objective: Our objective is to minimize the cost per day by finding the total daily cost such that we serving atleast 4 units of proteins per day (constraint 1) and the quantity of any input (steak and peanut butter) cannot go below 0 (constraint 2) because you cannot feed negative amounts of steak to anyone ๐
Constraints
While meeting our objective we have to make sure that we don’t voilate a couple of constraints.
Constraint | Description |
![]() | If we look at the problem definition we know that each pound of steak contains 2 units of proteins, and each pound of peanut butter contains 1 unit of proteins, so this constraint is telling us that we should always design a meal plan such that the user gets atleast 4 units of protein per day. |
![]() | The daily intake quantity of steak or peanut butter cannot go below 0 pounds, because we are dealing with linear equations – the model can try to explore options to minimize the cost by trying negative quantities of each input – while it is possible to get a low cost which meets the first constraint (providing atleast 4 units of proteins) but it can come up with negative quantities which are not possible in real world. |
Implementation
We will be implementing the model using Python and PuLP. This is a minimalistic example so we will not be needing any more libraries.
All the code for this article is present on the Machine Learning Guides github repository, so let’s start.
Environment Setup
I am using miniconda to create an isolated environment – you can use any environment manager available for python like venv or full anaconda. In the code directory on github you will find the environment.yml file, after installing anaconda simply run the following commands on your terminal.
conda install -y jupyter
You can now checkout the repository on you machine by running the following commands.
git clone https://github.com/the-geeks-diary/machine-learning-guides.git
cd .\articles\linear-programming\lp-part-1\
conda env create -f environment.yml -n optimization-python-pulp
conda activate optimization-python-pulp
python -m ipykernel install --user --name optimization-python-pulp --display-name "Python 3.10 (optimization-python-pulp)"
jupyter notebook
These commands simply checkout the code on your computer and create an anaconda environment with the correct python version (3.10), pip (>=22.0) and packages defined in environment.yml
file. We are using the following pacakges:
Coding The Model
We will start by importing the classes and functions defined in PuLP library, we will be needing the following:
Class/Function | Description |
LpProblem | This class abstracts a linear programming problem and is used to hold the variables and constraints, this also offers a function to invoke a solver to solve the problem. |
LpMinimize | This is a constant that defines that when solving the problem – our objective is to minimize the objective. |
LpVariable | This class abstracts a variable that constitutes the problem, there should be a linear relationship between the variable and the objective, example: in our case the pounds of steak affect the cost of the meal by the factor of price per pound of steak – so this is a linear relationship – the cost of the meal increases by a linear factor. |
LpStatus | This is a dictionary/map of numeric status codes returned by the LpProblem to their string representations, example status 1 means Optimal. |
LpContinuous | This is a constant denoting that the variable is a continous variable, a variable could be of one of the following types: 1. Continuous: example 1.001, 0.56, 2.88 etc 2. Integer: 1, 2, 3 etc. 3. Binary: 0 or 1 (or True or False) |
PULP_CBC_CMD | This is solver that implements Branch-and-Cut algorithm, you can read more about it at official documentation page. |
from pulp import LpProblem, LpMinimize, LpVariable, lpSum, LpStatus, LpContinuous, PULP_CBC_CMD
Defining Problem and Setting Objective
To define out problem I have created a simple function that takes in the following parameters:
- steak_price (float): price per pound of steak in dollars ($)
- peanut_butter_price (float): price per pund of peanut butter in dollars ($)
The function returns a tuple of problem, and 2 variables (S & P) – these variables denote the quantity of steak and peanut butter respectively. The code is something like:
def define_problem_objective(steak_price: float, peanut_butter_price: float):
problem = LpProblem(name="DietProblem", sense=LpMinimize)
S = LpVariable(name = "Steak_In_Pounds", lowBound = 0, cat = LpContinuous)
P = LpVariable(name = "Peanut_Butter_In_Pounds", lowBound = 0, cat = LpContinuous)
problem += (steak_price*S) + (peanut_butter_price * P), "MinimizeCost"
return (problem, S, P)
Let’s understand the function:
- We create a problem instance (LpProblem) and define it’s name “DietProblem” and indicate that we are trying to minimize the objective (cost) using
sense=LpMinimize
. - We create variable S to hold the quantity of Steak and give it a name “Steak_In_Pounds” and define the lowBound = 0 and indicate that this is continous variable using
cat=LpContinuous
. - We create variable P to hold the quantity of Peanut Butter and give it a name “Peanut_Butter_In_Pounds” and define the lowBound = 0 and indicate that this is continous variable using
cat=LpContinuous
. - We set the objective for the problem by defining how the our variables affect the cost i.e. the total cost = (price of steak X quantity of steak) + (price of peanut butter X quantity of peanut butter)
- We return the newly created problem and the variables for the problem.
Add Constraints
Now that we have the problem and objective, we need to define the constraints.
- Our first constraint is the the intake of proteins, each unit (pound) of steak contains 2 units of proteins and each unit of peanut butter contains 1 unit of protein.
- The quantities of steak or proteins cannot be less than 0.
We create a function and pass the problem and the variables to set these constaints as shown below:
def add_constraints(problem: LpProblem, S: LpVariable, P: LpVariable):
problem += (2*S) + P >= 4, "MinimumProteinIntake"
problem += S >= 0, "MinimumSteakQuantity"
problem += P >= 0, "MinimumPeanutButterQuantity"
Solve Problem at Different Price Points
We can now solve the problem at different price points as shown below.
prices = [(3,2), (4,2), (4,2.5), (12, 2), (10,3)]
for steak_price, peanut_butter_price in prices:
print("\n****************************************************")
print(f"Steak Price: {steak_price} | Peanut Butter Price: {peanut_butter_price}")
problem, steak, peanut_butter = define_problem_objective(steak_price, peanut_butter_price)
add_constraints(problem, steak, peanut_butter)
problem.solve(PULP_CBC_CMD(msg=0))
print(f"Status of solution is: {LpStatus[problem.status]}")
print(f"Optimal cost per day is: ${problem.objective.value()}")
print(f"Steak (in pounds): {steak.value()}")
print(f"Peanut Butter (in pounds): {peanut_butter.value()}")
****************************************************
Steak Price: 3 | Peanut Butter Price: 2
Status of solution is: Optimal
Optimal cost per day is: $6.0
Steak (in pounds): 2.0
Peanut Butter (in pounds): 0.0
****************************************************
Steak Price: 4 | Peanut Butter Price: 2
Status of solution is: Optimal
Optimal cost per day is: $8.0
Steak (in pounds): 2.0
Peanut Butter (in pounds): 0.0
****************************************************
Steak Price: 4 | Peanut Butter Price: 2.5
Status of solution is: Optimal
Optimal cost per day is: $8.0
Steak (in pounds): 2.0
Peanut Butter (in pounds): 0.0
****************************************************
Steak Price: 12 | Peanut Butter Price: 2
Status of solution is: Optimal
Optimal cost per day is: $8.0
Steak (in pounds): 0.0
Peanut Butter (in pounds): 4.0
****************************************************
Steak Price: 10 | Peanut Butter Price: 3
Status of solution is: Optimal
Optimal cost per day is: $12.0
Steak (in pounds): 0.0
Peanut Butter (in pounds): 4.0
In our code we are evaluating the problem at following price points.
Steak (price in dollars per pound) | Peanut Butter (price in dollars per pound) |
---|---|
3 | 2 |
4 | 3 |
4 | 2.5 |
12 | 2 |
10 | 3 |
As can be seen above the optimal choices affecting the cost change as the price per unit of steak and peanut butter changes.
Conclusion
This is the first in the series of articles that I would be publishing to cover the Linear programming concepts, in today article we saw a basic example of solving an optimization probelm, in coming weeks we would be diving deeper into more advanced problems with large number of variables and conclude this with Multi-Objective Optimization using Linear Programming wherein we would be optimizing multiple objective subject to various constraints.
If you have any questions or idea please post them in the comments and I would be happy to answer them or cover the new topics in the upcoming articles.
Leave a Reply