Linear Programming with Python and PuLP – Part 2

Introduction to PuLP

PuLP is an open source linear programming package for python. PuLP can be installed using pip, instructions here.

In this notebook, we’ll explore how to construct and solve the linear programming problem described in Part 1 using PuLP.

A brief reminder of our linear programming problem:

We want to find the maximum solution to the objective function:

$Z = 4x + 3y$

Subject to the following constraints:

$
x \geq 0 \\
y \geq 2 \\
2y \leq 25 – x \\
4y \geq 2x – 8 \\
y \leq 2x -5 \\
$

We’ll begin by importing PuLP

In [1]:

import pulp

Then instantiate a problem class, we’ll name it “My LP problem” and we’re looking for an optimal maximum so we use LpMaximize

In [2]:

my_lp_problem = pulp.LpProblem("My LP Problem", pulp.LpMaximize)

We then model our decision variables using the LpVariable class. In our example, x had a lower bound of 0 and y had a lower bound of 2.

Upper bounds can be assigned using the upBound parameter.

In [3]:

x = pulp.LpVariable('x', lowBound=0, cat='Continuous')
y = pulp.LpVariable('y', lowBound=2, cat='Continuous')

The objective function and constraints are added using the += operator to our model.

The objective function is added first, then the individual constraints.

In [4]:

# Objective function
my_lp_problem += 4 * x + 3 * y, "Z"

# Constraints
my_lp_problem += 2 * y <= 25 - x
my_lp_problem += 4 * y >= 2 * x - 8
my_lp_problem += y <= 2 * x - 5

We have now constructed our problem and can have a look at it.

In [5]:

my_lp_problem

Out[5]:

My LP Problem:
MAXIMIZE
4*x + 3*y + 0
SUBJECT TO
_C1: x + 2 y <= 25

_C2: - 2 x + 4 y >= -8

_C3: - 2 x + y <= -5

VARIABLES
x Continuous
2 <= y Continuous

PuLP supports open source linear programming solvers such as CBC and GLPK, as well as commercial solvers such as Gurobi and IBM’s CPLEX.

The default solver is CBC, which comes packaged with PuLP upon installation.

For most applications, the open source CBC from COIN-OR will be enough for most simple linear programming optimisation algorithms.

In [6]:

my_lp_problem.solve()
pulp.LpStatus[my_lp_problem.status]

Out[6]:

'Optimal'

We have also checked the status of the solver, there are 5 status codes:

Not Solved: Status prior to solving the problem.
Optimal: An optimal solution has been found.
Infeasible: There are no feasible solutions (e.g. if you set the constraints x <= 1 and x >=2).
Unbounded: The constraints are not bounded, maximising the solution will tend towards infinity (e.g. if the only constraint was x >= 3).
Undefined: The optimal solution may exist but may not have been found.

We can now view our maximal variable values and the maximum value of Z.

We can use the varValue method to retrieve the values of our variables x and y, and the pulp.value function to view the maximum value of the objective function.

In [7]:

for variable in my_lp_problem.variables():
    print "{} = {}".format(variable.name, variable.varValue)

x = 14.5
y = 5.25

In [8]:

print pulp.value(my_lp_problem.objective)

73.75

Same values as our manual calculations in part 1.

In the next part we’ll be looking at a more real world problem.

Introduction
Part 1 – Introduction to Linear Programming
Part 2 – Introduction to PuLP
Part 3 – Real world examples – Resourcing Problem
Part 4 – Real world examples – Blending Problem
Part 5 – Using PuLP with pandas and binary constraints to solve a scheduling problem
Part 6 – Mocking conditional statements using binary constraints