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:

1 2 3 |
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 :

1 |
sudo yum install glpk, glpk-utils |

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
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.

Hi Thomas,

Nice article about PuLP’s functionality.

Do you know how to set % tolerance for GLPK solver using PuLP? I am using Python 2.7.8 32-bit in Windows 7 OS. When run on the solver, my problem when run on the solver, converges to approx. 1% of the optimal quickly, however time to compute the exact optimal solution is quite high. Can you please suggest a solution?

No sorry.

hi, do you have an example of setting up problem in PULP with matrices? thanks.

No sorry. best

Hi Thomas,

How can I obtain the Z value? any idea?

Hi, I think the 3 constraints

prob += x1=0

prob += x2>=0

can be removed since these variables are already constrained by their domain definition (0 <= x1 <= 40 and 0 <= x2 <= 1000).

Best regards

Indeed, and the prob += x1<=40 as well. Thanks for spotting those redundant constraints.