Basic Linear Programming in Python with PuLP
PuLP is a python library which can be used to solve linear programming problems. Linear Programming is used to solve optimization problems and has uses in various industries such as Manufacturing, Transportation, Food Diets etc
A basic Linear Programming problem is where we are given multiple equations. The value of one of the equations has to be maximized or minimized while the other equations are constraints. In high school, we used to plot the equations on a graph, shade the feasible region and find the value of the equation to be maximized or minimized by substituting the variables with the verticle values of the shaded region. I briefly go over this technique in the first part of the tutorial
I will be dividing the tutorial into two parts
- A brief overview of Linear Programming
- Using PuLP to solve an optimization problem
Linear Programming is used to solve Optimization problems given a few constraints. An example problem is below:
- We have two models of a car, Car A and Car B.
- Car A gives us a profit of 20k and Car B gives us a profit of 45k
- The Designer takes 4 days to build Car A and 5 days to build Car B
- The Engineer takes 3 days to build Car A and 6 days to build Car B
- The Machine takes 2 days to build Car A and 7 days to build Car B
- The Designer, Engineer and Machine can all work for 30 days
Getting High School Flashbacks?
We need to maximize our Profits 💵 💵
The first point gives us our decision variables. The following point gives us our Objective Function which we need to maximize and the rest of the points give us our constraints.
One way to solve it is to plot the equations on a graph, find the feasible area and then plug in the value of the vertices.
Below is the feasible region shaded in green. The vertices are not necessarily integers and since we can not make cars in fractions, we can only accept integer solutions.
Finding the integer solutions is not so trivial, we can not round up the vertice values and consider it a solution since we may violate some constraints in doing so. Using PuLP, we will be able to easily find the integral solutions
PuLP is an open-source Python library used for Linear Programming. Documentation for the library can be found here.
Install and Import pulp
pip install pulp from pulp import *
Create an Instance of LpProblem
problem = LpProblem('Car Factory', LpMaximize)
The first parameter is the name of our problem and the second parameter is the type of the Problem. We need to maximize our profits, therefore we use LpMaximize
Create Decision Variables
A = LpVariable('Car A', lowBound=0 , cat=LpInteger)
B = LpVariable('Car B', lowBound=0 , cat=LpInteger)
The first parameter is the name of the variable, the second parameter specifies the lower bound and third parameter specifies the type of the variable. The type can also be LpContinuous or LpBinary.
Objective Function and Constraints
We add the objective function and constraints to the instance of the LpProblem we created earlier.
problem += 20000A + 45000B , 'Objective Function'
problem += 4A + 5B <= 30 , 'Designer Constraint'
problem += 3A + 6B <=30, 'Engineer Constraint'
problem += 2A + 7B <=30, 'Machine Constraint
Upon printing the problem variable to the terminal we get the following output
Car_Profit: MAXIMIZE 20000Car_A + 45000Car_B + 0 SUBJECT TO Designer_Constraint: 4 Car_A + 5 Car_B <= 30 Engineer_Constraint: 3 Car_A + 6 Car_B <= 30 Machine_Constraint: 2 Car_A + 7 Car_B <= 30 VARIABLES 0 <= Car_A Integer 0 <= Car_B Integer
We can also use the status attribute to check the current Status of our problem. It is an integer value and we will need to use LpStatus to map it to a meaningful message
print("Current Status: ", LpStatus[problem.status]) Current Status: Not Solved
Solve the Problem
We will use the solve method to solve the problem.
print("Number of Car A Made: ", A.varValue)
print("Number of Car B Made: ", B.varValue)
print("Total Profit: ", value(problem.objective))
The output is the following
Number of Car A Made: 1.0
Number of Car B Made: 4.0
Total Profit: 200000.0
If you print the status now, you should get the following output
Current Status: Optimal
In just a few lines of code, we were able to maximize the profits by making more or Car B as compared to Car A. PuLP has many other interesting applications as well. A couple of them are listed below