Solving Linear Programming using Python PuLP
Learn how to use Python PuLP to solve linear programming problems.
As Senior operation manager, your job is to optimize scarce resources, improve productivity, reduce cost and maximize profit. For example, you want to maximize the profit of the manufacturing unit with constraints like labor working hours, machine capacity, and available raw material. Another example, As a marketing manager wants to allocate the optimum budget among alternative advertising media channels such as radio, television, newspaper, and magazine. Such problems can be considered optimization problems.
Optimization problems can be represented as a mathematical function that captures the tradeoff between the decisions that need to be made. The feasible solutions of such problems depend upon constraints specified in mathematical form.
Linear programming is the core of any optimization problem. It is used to solve a wide variety of planning and supply chain optimization. Linear programming was introduced by George Dantzig in 1947. It uses linear algebra for determining the optimal allocation of scarce resources.
In this tutorial, we are going to cover the following topics:
Linear Programming
LP models are based on linear relationships. It assumes that the objective and the constraint function in all LPs must be linear. This mathematical technique is used to solve the constrained optimization problem. There are 4 basic assumptions of LP models:
- Additivity Assumption: The terms of objective function and constraints must be additive. e.g. total consumption must equal to sum of the profits from each decision variable and total contributions to the problem objective, resulting by carrying out each activity independently.
- Proportionality Assumption: Each decision variable has a linear impact in the linear objective function and in each constraint. The consumptions and contributions for each activity are proportional to the actual activity level.
- Divisibility Assumption: Decision variables may accept the non-integer value. Each variable is allowed to have fractional values (continuous variables).
- Certainty Assumption: Each coefficient of the objective vector and constraint matrix is known with certainty (not a random variable) (https://link.springer.com/book/10.1007/978-3-319-68837-4). Model parameters are known and constrained. Relevant constraints have been identified and represented in the model.
Methods for Solving Linear Programming Problems
These are the following methods used to solve the Linear Programming Problem:
- Graphical Method
- Simplex Method
- Karmakar’s Method
Graphical is limited to the two-variable problem while simplex and Karmakar’s method can be used for more than two variables.
Components of Linear Programming
- Decision Variables: What you can control.
- Objective Function: math expressions that use variables to express goals.
- Constraints: math expressions that describe the limit of a solution.
Modeling Linear Programming Using Python PuLP
There are various excellent optimization python packages are available such as SciPy, PuLP, Gurobi, and CPLEX. In this article, we will focus on the PuLP python library. PuLP is a general-purpose and open-source Linear Programming modeling package in python.
Install pulp package:
!pip install pulp
PuLP modeling process has the following steps for solving LP problems:
- Initialize Model
- Define Decision Variable
- Define Objective Function
- Define the Constraints
- Solve Model
Understand the problem
This problem is taken from Introduction to Management Science By Stevenson and Ozgur.
A furniture company produces a variety of products. One department specializes in wood tables, chairs, and bookcases. These are made using three resources labor, wood, and machine time. The department has 60 hours of labor available each day, 16 hours of machine time, and 400 board feet of wood. A consultant has developed a linear programming model for the department.
x1= quantity of tables
x2= quantity of chairs
x3= quantity of bookcases
Objective Function: Profit = 40*x1+30*x2+45*x3
Constraints:
- labor: 2*x1 + 1*x2 + 2.5*x3 <= 60 Hours
- Machine: 0.8*x1 + 0.6*x2 + 1.0*x3 <= 16 Hours
- Wood: 30*x1 + 20*x2 + 30*x3 <= 400 board-feet
- Tables: x1>=10 board-feet
- x1, x2, x3 >= 0
Initialize Model
In this step, we will import all the classes and functions of pulp
module and create a Maxzimization LP problem using LpProblem class.
# Import all classes of PuLP module
from pulp import *
# Create the problem variable to contain the problem data
model = LpProblem("FurnitureProblem", LpMaximize)
Define Decision Variable
In this step, we will define the decision variables. In our problem, we have three variables wood tables, chairs, and bookcases. Let’s create them using LpVariable
class. LpVariable
will take the following four values:
- First, arbitrary name of what this variable represents.
- Second is the lower bound on this variable.
- Third is the upper bound.
- Fourth is essentially the type of data (discrete or continuous). The options for the fourth parameter are
LpContinuous
orLpInteger
.
# Create 3 variables tables, chairs, and bookcases
x1 = LpVariable("tables", 0, None, LpInteger)
x2 = LpVariable("chairs", 0, None, LpInteger)
x3 = LpVariable("bookcases", 0, None, LpInteger)
Define Objective Function
In this step, we will define the maximum objective function by adding it to the LpProblem
object.
# Create maximize objective function
model += 40 * x1 + 30 * x2 + 45 * x3
Define the Constraints
In this step, we will add the 4 constraints defined in the problem by adding them to the LpProblem
object.
# Create three constraints
model += 2 * x1 + 1 * x2 + 2.5 * x3 <= 60, "Labour"
model += 0.8 * x1 + 0.6 * x2 + 1.0 * x3 <= 16, "Machine"
model += 30 * x1 + 20 * x2 + 30 * x3 <= 400, "wood"
model += x1 >= 10, "tables"
Solve Model
In this step, we will solve the LP problem by calling solve() method. We can print the final value by using the following for loop.
# The problem is solved using PuLP's choice of Solver
model.solve()
# Each of the variables is printed with it's resolved optimum value
for v in model.variables():
print(v.name, "=", v.varValue)
Output: bookcases = 0.0 chairs = 5.0 tables = 10.0
Summary
Congratulations, you have made it to the end of this tutorial!
In this article, we have learned Linear Programming, its assumptions, components, and implementation in the python PuLp library. We have solved the Linear programming problem using PuLP. Of course, this is just the beginning, and there is a lot more that we can do using PuLP in Optimization and Supply Chain. In upcoming articles, we will write more on different optimization problems and its solution using Python. You can revise the basics of mathematical concepts in this article.