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.

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

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:

• PuLP

Coding The Model

We will start by importing the classes and functions defined in PuLP library, we will be needing the following:

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:

1. 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.
2. 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.
3. 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.
4. 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)
5. 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.

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.