Solving a Linear Programming problem with Python (Pulp)

Linear Programming is a type of optimisation where an objective function should be maximised given some constraints. Let us consider the following simple problem (from The GNU Linear Programming Kit, Part 1). Let us say that you want to maximize profits by selling wood soldiers (denoted x1) and wood trains (denoted x2) given that the margin is 3$ for one soldier and 2$ for one train, you want to maximize the profit. In addition, you have the following constraints per week:

• a soldier requires 2 hours of finishing labour. a train requires 1 hour of finishing labour. You have only 100 hours of finishing labour avaiable weekly
• a soldier requires 1 hour of carprentry labour. Same for a train. You have only 80 hours of carpentry labour available weekly
• demand for soldiers not more than 40 per week

The constraints can be transformed into equations:

  2*x1 + x2 <= 100
  x1 + x2 <= 80
  x1 <=40

and of course, x1>=0 and x2=0 otherwise there is nothing to optimise.

In The GNU Linear Programming Kit, Part 1, the author uses glpk to solve this problem. However, I found this Python library called pulp that provides a nice interface to glpk and other libraries. I’m going to solve the problem with pulp. First, we need to install glpk. Under Fedora, you need to install glpk and glpk-utils :

sudo yum install glpk, glpk-utils

Then, the following python script using pulp solves the problem. The code is self explanatory:

from pulp import *
 
# declare your variables
x1 = LpVariable("x1", 0, 40)   # 0<= x1 <= 40
x2 = LpVariable("x2", 0, 1000) # 0<= x2 <= 1000
 
# defines the problem
prob = LpProblem("problem", LpMaximize)
 
# defines the constraints
prob += 2*x1+x2 <= 100 
prob += x1+x2 <= 80
 
 
# defines the objective function to maximize
prob += 3*x1+2*x2
 
# solve the problem
status = prob.solve(GLPK(msg=0))
LpStatus[status]
 
# print the results x1 = 20, x2 = 60
value(x1)
value(x2)

It works like a charm ! x1=20, x2=60 as expected.

Please follow and like us: