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:

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 :

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

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

This entry was posted in Data analysis and tagged , . Bookmark the permalink.

7 Responses to Solving a Linear Programming problem with Python (Pulp)

  1. Akhil says:

    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?

  2. luq says:

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

  3. William says:

    Hi Thomas,

    How can I obtain the Z value? any idea?

  4. Jean Ibarz says:

    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

Leave a Reply

Your email address will not be published.