Linear Programming in Python using PuLP – Part 1


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.

ParameterTypeDescription
Vitamin B-12ObjectiveMaximize the content of Vitamin B-12 in patient’s meals
Vitamin B-12ConstraintThe total Vitamin B-12 content should not be less than 2.4 mg in all meals combined for any given day.
Number of MealsConstraintWe have to meet the objective by feeding exactly 3 meals (no less no more) to the patient per day (breakfast, lunch, dinner)
CaloriesConstraintThe total calories content in all meals combined should not be less than 2500 calories (given that our patient is an adult male)
Problem Definition

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

TermMeaning
ObjectiveObjective 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.
ConstraintA 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
Concepts of Linear Programming

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.

ConstraintDescription
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.
Constraints Definition

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/FunctionDescription
LpProblemThis 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.
LpMinimizeThis is a constant that defines that when solving the problem – our objective is to minimize the objective.
LpVariableThis 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.
LpStatusThis is a dictionary/map of numeric status codes returned by the LpProblem to their string representations, example status 1 means Optimal.
LpContinuousThis 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_CMDThis is solver that implements Branch-and-Cut algorithm, you can read more about it at official documentation page.
Imported Classess and Functions from PuLP package
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.

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.

, , , ,


One response to “Linear Programming in Python using PuLP – Part 1”

  1. […] In the previous article, we covered the basics of Linear Programming using PuLP in Python. In this follow-up article, we will delve deeper into the Pulp library and explore some advanced features and techniques for solving linear programming problems. Here is a summary of what we covered in the previous post. […]

Leave a Reply

Other posts

  • Object Extraction using Image Segmentation: A Comprehensive Tutorial with Detectron2 and Mask2Former

    Object Extraction using Image Segmentation: A Comprehensive Tutorial with Detectron2 and Mask2Former

    Discover how to perform object extraction using image segmentation with Detectron2 and Mask2Former in our step-by-step tutorial. Learn to set up the environment, configure the model, and visualize segmentation results, extracting objects from images with ease. Boost your computer vision skills and optimize your image processing projects with this comprehensive guide.

  • Building Your First Neural Network with TensorFlow – Deep Learning 2

    Building Your First Neural Network with TensorFlow – Deep Learning 2

    Neural networks are a fundamental concept in deep learning and are used for a wide range of applications such as image and speech recognition, natural language processing, and much more. In this article, we will walk you through the process of building your first neural network using TensorFlow, a popular open-source machine learning library. We'll…

  • Introduction to Deep Learning with TensorFlow – Deep Learning 1

    Introduction to Deep Learning with TensorFlow – Deep Learning 1

    In this article, we provide an introduction to deep learning with TensorFlow. We cover what deep learning is, what it can do, why TensorFlow is a great choice for deep learning, and an overview of TensorFlow itself. We also explore the different types of neural networks used in deep learning, and demonstrate how to build…

  • How To: Set Up PyTorch with GPU Support on Windows 11 – A Comprehensive Guide

    How To: Set Up PyTorch with GPU Support on Windows 11 – A Comprehensive Guide

    Introduction Hello tech enthusiasts! Pradeep here, your trusted source for all things related to machine learning, deep learning, and Python. As you know, I’ve previously covered setting up TensorFlow on Windows. Today, I’m excited to bring you a detailed guide on setting up another popular deep learning framework, PyTorch, with GPU support on Windows 11.…

  • Solving a Complex Logistics Optimization Problem using the Pulp Library in Python – Part 4

    Solving a Complex Logistics Optimization Problem using the Pulp Library in Python – Part 4

    In this article, we demonstrate how to solve a logistics optimization problem using the Pulp library in Python. By defining the variables, objective function, and constraints, and using the solve method to find the optimal solution, we are able to minimize the total cost of transportation while satisfying the constraints. This article concludes the multi-part…

  • Linear Programming in Python using PuLP โ€“ Part 3: Optimizing Investment Portfolios with Multi-Objective Optimization

    Linear Programming in Python using PuLP โ€“ Part 3: Optimizing Investment Portfolios with Multi-Objective Optimization

    In this article, we used the Pulp library in Python to solve a linear programming problem to find the optimal investment portfolio. We defined variables, added constraints, defined objectives, and solved the problem to find the optimal solution that balances the trade-off between maximizing returns and minimizing risk. The code was concise and easy to…

  • Linear Programming in Python using Pulp – Part 2

    Linear Programming in Python using Pulp – Part 2

    In this article, we delve deeper into linear programming and explore how to solve a multi-objective optimization problem using the Pulp library in Python. We present a problem in which a nutritionist must find the optimal meal plan for a patient suffering from anemia, balancing the intake of Vitamin B12 and fat. We demonstrate how…

  • Linear Programming in Python using PuLP – Part 1

    Linear Programming in Python using PuLP – Part 1

    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…

  • How To: Setup Tensorflow With GPU Support using Docker

    How To: Setup Tensorflow With GPU Support using Docker

    Previously I published a guide for setting up tensorflow in an anconda environment with GPU support. A lot of people liked it and I have been working with this environment myself for more than a year now. I am happy with the results however the process is a bit involved and requires quite a bit…

  • How To: Setup Tensorflow With GPU Support in Windows 11

    How To: Setup Tensorflow With GPU Support in Windows 11

    It's been just 2 days since Windows 11 came out and I am already setting up my system for the ultimate machine learning environment. Today we are going to setup a new anaconda environment with tensorflow 2.5 with GPU support using NVIDIA CUDA 11.4 and CUDNN 8.2.4 along with Python 3.8. This is going to…

  • Tools of The Trade – II

    Tools of The Trade – II

    In continuation of my previous post today I will talk about the website tanooja.com. I did this project on request of my wife because she wanted to pursue blogging and didn't want to go through the ordeal needed to write, publish and manage SEO using most of the prominent blogging platforms like WordPress, Joomla, Drupal…

  • Tools of The Trade – I

    Tools of The Trade – I

    In this post I will share a few tools and technologies that I am using to run a couple of blazing fast websites using latest modern tools and technologies. The caveat here is that I don't pay any infrastructure/hosting costs for any of these websites and they can scale infinitely in terms of supported users…

  • Building Lizzie – IV

    Building Lizzie – IV

    Another post about Lizzie. I started off with a Raspberry Pi 3 to build a personal assistant for my car and I have come a long way both in terms of the concept and the functionality. Most importantly I have formalized the application flow and also extended the scope from one device to almost all…

  • OBD-II with Raspberry Pi3

    OBD-II with Raspberry Pi3

    I am writing this article in response to a question posted on my YouTube channel. Here I would be talking about communicating to an OBD-II device (ELM327 chip with Bluetooth) hooked into your car’s OBD-II port. The OS I am using is Windows 10 IoT core. This information is important because it makes a difference…

  • Building Lizzie – III

    Building Lizzie – III

    As mentioned in previous article today I would be talking about OBD-II integration in Lizzie using a Bluetooth serial communication with an ELM327 adapter that fits on a OBD-II port in your car. OBD stands for On Board Diagnostics which is connected to the ECU (Engine Control Unit) and provides a ton of information (both…

  • Building Lizzie – II

    Building Lizzie – II

    In the previous post I described my experiments around building an intelligent artificial personal assistant – Lizzie. The pseudo intelligent agents available today around us (Siri, Cortana or Google Next) are all great feats of engineering given the fact that they reside on small devices like mobile phones and are able to do powerful things…

  • Building Lizzie – I

    Building Lizzie – I

    Recently I have been busy building a personal assistant that I would be fitting in my car. Currently I am in experimentation mode and I am experimenting with speech capabilities. I would start with a description of my journey so far. First let me show off a little bit with these videos that I created…

  • How To: Super Fast Tensorflow 2 Setup with GPU Support in VS Code

    I am publishing this article in response to a comment I received on How To: Setup Tensorflow With GPU Support using Docker article. Docker is all good and nice but all of us agree that we use IDEs (integrated dev environment – think VSCode) on our machines. So let’s say you want to get the…

%d bloggers like this: