Linear Programming in Python with PuLP

We all have to make choices almost everyday in our lives. These choices might allow us to maximize one thing while requiring us to sacrifice another. Whenever we are making such choices, we are performing optimization

Most people who want to buy a new house and are considering parameters such as

• price
• location
• nearby schools
• proximity to shopping malls
• proximity to hospitals
• neighborhood security

Value assigned for above listed parameters are different by different users , However, the ultimate goal is to choose the best possible option from the available choices , If same is represented in mathematical terms, It can be solved using linear programming

What is?PuLP?

PuLP?is a free, open-source library that solves optimization problems computationally.

To use PuLP

1. Need to create a mathematical model of an optimization problem that includes the optimization variables & constraints.
2. Need to use an optimizer to solve the linear programming problems

Getting started with PuLP

pip install pulp
from pulp import *        

Most commonly used optimization algorithms in LP

Simplex Algorithm

The Simplex algorithm involves the selection of a random corner point of the feasible region. The feasible region (or the polygonal region) corresponds to the constraints that are graphically specified. Each corner of the region represents a solution—a possible optimal solution will be one of them

Ellipsoid Algorithm

The?ellipsoid?algorithm works by creating an ellipsoid inside the plot so that it contains the feasible region. After that, it checks the center of the ellipsoid to see if it contains the feasible region. If it does, the optimal solution has been found and no further steps need to be taken. If not, a half-ellipse is chosen to fit the ellipse. If the volume of the ellipsoid is significantly reduced after multiple iterations and no solution optimizes the problem, it indicates that the linear optimization problem does not have an optimal solution.

Interior-point algorithm

The?interior-point algorithm?is a combination of both the simplex algorithm and ellipsoid algorithm. It can be used to solve both linear and non-linear convex optimization problems. The major modification from the simplex method is that instead of searching for the optimal solution in the corners of the feasible region, this algorithm performs the search inside it.?

Geometric solution

In Geometric solution constraints of an n-variable problem are plotted in an n-dimensional plane. The points lying in the region of intersection of all these plots satisfy the constraints simultaneously. So, the optimal solution to the problem is either the largest among the points of intersection in the case of maxima or the farthest from them in the case of minima.

Solvers in PuLP

PuLP employs an API solver from an available list of optimizers to solve the given linear programming problem. We can use solvers by specifying them as an argument in the?solve?method

• Gurobi

import gurobiby as grb
opt_model = grb.Model(name="MIP Model")        

• CPLEX

import docplex.mp.model as cp
opt_model = cpx.Model(name="MIP Model")        

• MOSEK
• CBC
• GLPK
• CLP
• FICO XPRESS
• Choco SolverMIPCL
• SICP

Example 1

Consider a Tesla manufacturing system where the it wants to maximize their profits.?

The following points summarize the problem:

• There are two model Model U and Model Z
• Model U gives Tesla profit of $20K while Model Z gives Tesla profit of $45K
• Factory Engineer takes 4 days to build Model U and?5 days to build Model Z?
• Machine Takes 3 days to build Model U and 6 days to build Model Z?
• Quality team takes 2 days test Model U and 7 days test Model Z
• Engineer , Machine and Quality can all work for 30 days?

To maximize profits?

Step 1:?The first point gives us our decision variables while the remaining points give us the objective function, which we need to maximize.

20000 A + 45000 B?with constraints?

• A,B > 0
• 4 A + 5 B <= 30?
• 3 A?+ 6 B <=30
• 2A + 7B <=30

from pulp import *
# Step 1: Creating an instance of an LP problem?
problem = LpProblem('Tesla_Factory', LpMaximize) 
# Step 2: Creating decision variables
U = LpVariable('Model_U', lowBound=0 , cat=LpInteger)
Z = LpVariable('Model_Z, lowBound=0 , cat=LpInteger)  
# Step 3: Specifying objective function and constraints
problem += 20000*U + 45000*Z , 'Objective Function' 
#Constraints
problem += 4*U + 5*Z <= 30, 'Designer Constraint'
problem += 3*U + 6*Z <=30, 'Engineer Constraint'
problem += 2*U + 7*Z <=30, 'Machine Constraint'
print("Current Status: ", LpStatus[problem.status])
# Solving the problem
problem.solve(PULP_CBC_CMD(msg=False))
print("Current Status: ", LpStatus[problem.status])
print("Number of Model U Made: ", A.varValue)
print("Number of Model Z Made: ", B.varValue)
print("Total Profit: ", value(problem.objective))
        

Output

Current Status:? Not Solved
Current Status:? Optimal
Number of Model U Made:? 1.0
Number of Model Z Made:? 4.0
Total Profit:? 200000.0