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 or Maximize 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.Minimize |

Constraint | A constraint is a condition that you would like to 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 dayfulfill |

### 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

**respectively.**

*P*

- Let
be the number of pounds ofSsteakper day.- Let
be the number of pounds ofPpeanut butterper 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

**is 2 currency units. So our goal is to:**

*price per pound of peanut butter*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)
the pounds of inputs (steak and peanut butter)**times** - 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