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

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

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.

#Objective Function
problem += 20000*A + 45000*B , 'Objective Function'
#Constraints
problem += 4*A + 5*B <= 30 , 'Designer Constraint'
problem += 3*A + 6*B <=30, 'Engineer Constraint'
problem += 2*A + 7*B <=30, 'Machine Constraint

Upon printing the problem variable to the terminal we get the following output

Car_Profit:
MAXIMIZE
20000*Car_A + 45000*Car_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.

problem.solve()
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

Conclusion 

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 

• Sudoku Solver: Use Linear Programming to solve the famous Sudoku Puzzles
• Diet Plan: Create a diet plan such that various constraints on calorie and nutrition intake are met while minimizing the cost