Example of use of the Pulp libray for a simple knapsack problem

#Install pulp
!pip install pulp

# Import libraries
from pulp import *
import time

Collecting pulp
  Downloading PuLP-2.8.0-py3-none-any.whl (17.7 MB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 17.7/17.7 MB 19.9 MB/s eta 0:00:00
Installing collected packages: pulp
Successfully installed pulp-2.8.0

Let set up our problem with the decision variables (items), with their value “v” and weight “w”. We then set up the capacity of our bagpack.

# A list of tuples of items (value, weight)
# (value, volume)
items = [(3,4), (8,5), (10,1.5), (2,0.5), (7,1),
 (10,2), (5,1.5), (9,1), (9,0.5), (6,0.5)]

# number of items
itemCount = len(items)

# Knapsack max weight capacity
binCapacity = 7

Here we set up our decision variables (the X), the lower and upper bounds, couple with the integer constrains (cat=Integer) tells us the decision variable will be binary.

# Decision variables (array), x[i] gets 1 when item i is included in the solution
x = pulp.LpVariable.dicts('item', range(itemCount),
                            lowBound = 0,
                            upBound = 1,
                            cat = 'Integer')

Here we set up our problem (it is of maximization type, and it is a linear programming problem).

We add the objective function (sum of the values), and the constraint (sum of the weights).

# Initialize the problem and specify the type
problem = LpProblem("Knapsack Problem", LpMaximize)

# Add the objective function
problem += lpSum([ x[i] * (items[i])[0] for i in range(itemCount) ]), "Objective: Maximize profit"

# Capacity constraint: the sum of the weights must be less than the capacity
problem += lpSum([ x[i] * (items[i])[1] for i in range(itemCount) ]) <= binCapacity, "Constraint: Max capacity"

Here we write the problem as an lp file and we then solve it, using the “solve” function. We also keep track of the time it takes.

#print problem.constraints

# Write the model to disk, not necessary
problem.writeLP("Knapsack.lp")

# Solve the optimization problem
start_time = time.time()
problem.solve()
print("Solved in %s seconds." % (time.time() - start_time))

Solved in 0.011299371719360352 seconds.

Finally, we report on the optimal solution, and whether each variable was chosen or not

# Was the problem solved to optimality?
print("Status:", LpStatus[problem.status])

# Each of the variables is printed with it's resolved optimum value
for v in problem.variables():
    print(v.name, "=", v.varValue)

# The optimised objective function value is printed to the screen
print("Total profit = ", value(problem.objective))

Status: Optimal
item_0 = 0.0
item_1 = 0.0
item_2 = 1.0
item_3 = 1.0
item_4 = 1.0
item_5 = 1.0
item_6 = 0.0
item_7 = 1.0
item_8 = 1.0
item_9 = 1.0
Total profit =  53.0

Here, somore more info about the solution

used_cap = 0.0
print("Used items:")
for i in range(itemCount):
    if x[i].value() == 1:
        print(i, items[i])
        used_cap += items[i][1]
print("Profit: %d - Used capacity: %d (/ %d)" % (value(problem.objective), used_cap, binCapacity))

Used items:
2 (10, 1.5)
3 (2, 0.5)
4 (7, 1)
5 (10, 2)
7 (9, 1)
8 (9, 0.5)
9 (6, 0.5)
Profit: 53 - Used capacity: 7 (/ 7)