PuLP - Linear Programming with Python

Are you wondering whether this would be useful for Data Science or not? The answer is “Yes”. This article will be highly useful in Data Science. In this article, you will learn how to use PuLP and where this can be used.

When solving Data Science problems, we often come to a point where there are a lot of constraints and you are trying to maximize or minimize the cost. Here, you can use PuLP to solve for an optimized solution. The PuLP helps us to write mathematical expressions in Python language. There are many commercial and other open-source solvers available too for solving the optimization.

Let’s see how we can approach and solve a problem using PuLP. This involves a few steps:

• Understanding the problem
• Converting the problem into a mathematical expression
• Solving optimization
• Post-process to extract the solution

In linear programming, the decision variables should be real, objective and constraints should be linear. We can also do Integer programming, in which some or all of the decision variables are integers.

Now, we will discuss how to convert a problem into a linear program and solve it using PuLP. I will guide you through a simple example, which can be extended to a complicated problem.

For example, you went to a shop. There are ten different chocolates. Your goal is to buy chocolates such that the number of calories is maximized. Some of the constraints are:

• You can buy only 5 chocolates
• The cost should be less than or equal to 100

How to solve this? In general, we take 10 variables refering to each chocolate type. After that, we define the above linear constraints and solve the optimization. Let's do the same thing step by step using PuLP.

Let's code it in Python using PuLP. We will start by importing libraries.

# Import libraries
import pulp
import pandas as pd

First of all, we should initialize PuLP object and choose whether we want to minimize or maximize.

# Initalize PuLP object
optimization_model = pulp.LpProblem('MaximizeCalories', pulp.LpMaximize)

I have defined few constants below. The number of chocolates are 10. I took some random cost and calories for each chocolate, in two separate lists.

# Constants
number_of_chocolates = 10
cost_of_each_chocolate = [10, 16, 20, 25, 22, 18, 35, 40, 40, 24]
calories_of_each_chocolate = [100, 85, 200, 165, 78, 45, 80, 105, 65, 120]

Now, we create 10 decision variables (c_0, c_1, c_2, c_3, c_4, c_5, c_6, c_7, c_8, c_9) that will be used to define optimization function and constraints. Each decision variable refers to a chocolate. We store them in a list for easy accessibility. Also, please note that we are defining integer variables to be either 0(lowBound) or 1(upBound), so that the chocolate will be selected or rejected. We can also create variables that hold real numbers. We can choose it based on the problem we are solving.

# Create decision variables
decision_variables = []
for i in range(number_of_chocolates):
    variable = 'c' + '_' + str(i)
    variable = pulp.LpVariable(str(variable), lowBound = 0, upBound = 2, cat= 'Binary')
    decision_variables.append(variable)

After creating the decision variables, we define an optimization function and add it to the PuLP object(optimization_model). Our aim is to maximize the number of calories. So, we multiply each decision variable with it's respective calorie value. The optimization function would look like this. (c_0*v_0 + c_1*v_1 + c_2*v_2 + c_3*v_3 + c_4*v_4 + c_5*v_5 + c_6*v_6 + c_7*v_7 + c_8*v_8 + c_9*v_9). "c" refers to the decision variable and "v" refers to it's calorie value. After optimization, only some of the decision variables will be one. Their sum of calorie value is the maximum value.

# Optimization function
optimization_function = ""
for i in range(number_of_chocolates):
    formula = decision_variables[i] * calories_of_each_chocolate[i]
    optimization_function += formula
    
optimization_model += optimization_function

It's time to add our constraints to the optimization model. The first constraint is "We can select only 5 chocolates". The mathematical expression of this constraint would look as (c_0 + c_1 + c_2 + c_3 + c_4 + c_5 + c_6 + c_7 + c_8 + c_9 = 5). This constraint will make sure that we select only 5 variables (chocolates).

The second constraint is "The cost should be less than or equal to 100". The mathematical form of this constraint is similar to the optimization function(c_0*cost_0 + c_1*cost_1 + c_2*cost_2 + c3*cost_3 + c4*cost_4 + c5*cost_5 + c6*cost_6 + c7*cost_7 + c8*cost_8 + c9*cost_9 <= 100). "c" refers to the decision variable and "cost" refers to the price of that chocolate.

# Constraints
formula = ""
for i in range(number_of_chocolates):
    formula += (decision_variables[i])
optimization_model += (formula == 5)

formula = ""
for i in range(number_of_chocolates):
    formula += (cost_of_each_chocolate[i] * decision_variables[i])
optimization_model += (formula <= 100)

We have defined our optimization function and constraints. It's time to solve the optimization. We can do this by calling the solve method.

# Solve optimization
optimization_result = optimization_model.solve()

The solution can be optimal, not solved or infeasible. Let's check what we get. We will also print the maximum number of calories we can get.

print("Status:", pulp.LpStatus[optimization_model.status])
print("Total number of calories: ", pulp.value(optimization_model.objective))

Status: Optimal
Total number of calories: 670.0

The solution is optimal in this case. But, when we solve some complicated problems with alot of constraints, we may end up with "infeasible" solution. In that case, we need to either change the optimization function or constraints to make it optimal. It depends on the use case you are trying to solve.

# Let's see which decision variables are selected by the optimization
chocolate_is_selected = []
for var in optimization_model.variables():
    if (var.varValue == 1):
        print(var, end=" ")
    chocolate_is_selected.append(var.varValue)
print("\n")
print(chocolate_is_selected)

c_0 c_1 c_2 c_3 c_9
[1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0]

The optimization selected 5 decision variables that maximizes the number of calories(i.e 670 calories) by just spending less than 100 rupees. We will see how much we need to spend for those 5 chocolates below.

total_cost = (pd.Series(cost_of_each_chocolate)*pd.Series(chocolate_is_selected)).sum()
print(total_cost)

95

This is the end of this article. I hope you enjoyed reading this and learnt something new. If you have any queries, comment in the comments section below. I would be more than happy to answer your queries.

Thank you for reading my blog and supporting me. Stay tuned for my next article. If you want to receive email updates, don’t forget to subscribe to my blog. Keep learning and sharing!!

Follow me here:
GitHub: https://github.com/Abhishekmamidi123
LinkedIn: https://www.linkedin.com/in/abhishekmamidi/
Kaggle: https://www.kaggle.com/abhishekmamidi
If you are looking for any specific blog, please do comment in the comment section below.