Knapsack in PuLP, adding Constraints on Number of Items selected

Question

I have some puLP code, which solves my knapsack problem.

prob = LpProblem("Knapsack problem", LpMaximize)

x1 = LpVariable("x1", 0, 12, 'Integer')
x2 = LpVariable("x2", 0, 12, 'Integer')
x3 = LpVariable("x3", 0, 12, 'Integer')
x4 = LpVariable("x4", 0, 12, 'Integer')
x5 = LpVariable("x5", 0, 12, 'Integer')
x6 = LpVariable("x6", 0, 12, 'Integer')
x7 = LpVariable("x7", 0, 12, 'Integer')
x8 = LpVariable("x8", 0, 12, 'Integer')
x9 = LpVariable("x9", 0, 12, 'Integer')
x10 = LpVariable("x10", 0, 12, 'Integer')
x11 = LpVariable("x11", 0, 12, 'Integer')
x12 = LpVariable("x12", 0, 12, 'Integer')
x13 = LpVariable("x13", 0, 12, 'Integer')
x14 = LpVariable("x14", 0, 12, 'Integer')
x15 = LpVariable("x15", 0, 12, 'Integer')
x16 = LpVariable("x16", 0, 12, 'Integer')
x17 = LpVariable("x17", 0, 12, 'Integer')
x18 = LpVariable("x18", 0, 12, 'Integer')
x19 = LpVariable("x19", 0, 12, 'Integer')
x20 = LpVariable("x20", 0, 12, 'Integer')
x21 = LpVariable("x21", 0, 12, 'Integer')
x22 = LpVariable("x22", 0, 12, 'Integer')
x23 = LpVariable("x23", 0, 12, 'Integer')
x24 = LpVariable("x24", 0, 12, 'Integer')
x25 = LpVariable("x25", 0, 12, 'Integer')

prob += 15 * x1 + 18 * x2 + 18 * x3 + 23 * x4 + 18 * x5 + 20 * x6 + 15 * x7 + 16 * x8 + 12 * x9 + 12 * x10 + 25 * x11 + 25 * x12 + 28 * x13 + 35 * x14 + 28 * x15 + 28 * x16 + 25 * x17 + 25 * x18 + 25 * x19 + 28 * x20 + 25 * x21 + 32 * x22 + 32 * x23 + 28 * x24 + 25 * x25, "obj"

prob += 150 * x1 + 180 * x2 + 180 * x3 + 230 * x4 + 180 * x5 + 200 * x6 + 150 * x7 + 160 * x8 + 120 * x9 + 120 * x10 + 250 * x11 + 250 * x12 + 280 * x13 + 350 * x14 + 280 * x15 + 280 * x16 + 250 * x17 + 250 * x18 + 250 * x19 + 280 * x20 + 250 * x21 + 320 * x22 + 320 * x23 + 280 * x24 + 250 * x25 == 6600, "c1"

prob.solve()

print "Status:", LpStatus[prob.status]

for v in prob.variables():
    print v.name, "=", v.varValue

print ("objective = %s" % value(prob.objective))

But to this code I need append another restriction: For example, a restriction That the number of non-zero prob.variables must equal (say) 10.

Could anybody help with that?

UPDATE:

For this code I have output:

Status: Optimal
X1 = 1.0
x10 = 0.0
x11 = 0.0
x12 = 0.0
x13 = 0.0
x14 = 0.0
x15 = 0.0
x16 = 0.0
x17 = 0.0
x18 = 0.0
x19 = 0.0
x2 = 0.0
x20 = 0.0
x21 = 0.0
x22 = 0.0
x23 = 0.0
x24 = 0.0
x25 = 0.0
x3 = 0.0
x4 = 11.0
x5 = 0.0
x6 = 10.0
x7 = 0.0
x8 = 12.0
x9 = 0.0
objective = 660.0

The number of prob.variables that have non-zero values equals only 4. But say I need 10, how would I ensure that?

Answer 1

If you want a certain number of non-zero values, you can do that by introducing new 0/1 variables.

Formulation

Introduce 25 new Y variables [y1..y25] which are all binary {0,1}

If X[i] > 0, we want Y[i] to take on the value 1. You can do by adding the following constraints.

x[i] < y[i] x M (where M is some big number, say 10,000) for 1 in 1..25

Now, to ensure that at least 10 Y values are non-zero, we want at least 10 of them to be 1.

Sum over Y[1]...y[25] >= 10 will ensure that.

In PuLP The puLP code is untested, but will give you the right idea to proceed.

x=[]
y=[]

for index in range(25):
    y[index] = LpVariable("y"+str(index), 0, 1) #binary variables
    prob += x[index] <= 10000 * y[index], "If x%s is non-zero, then y%s is forced to be 1",%index, %index

prob += lpSum([y[i] for i in range(25)]) >= 10,"Ensuring at least 10 items are non-zero"

Hope that helps.

Answer 2

I second the provided answer, but also would comment on making better use of PuLP's (and Python's) list comprehensions for shorter code:

from pulp import *
prob = LpProblem("Knapsack problem", LpMaximize)
cost = [15,18,18,23,18,20,15,16,12,12,25,25,28,35,28,28,25,25,25,28,25,32,32,28,25]
x = LpVariable.dicts('x',range(1,26),lowBound=0,upBound=12,cat=pulp.LpInteger)
cap = [150,180,180,230,180,200,150,160,120,120,250,250,280,350,280,280,250,250,250,280,250,320,320,280,250] 
prob += pulp.lpSum([cost[ix]*x[ix] for ix in range(1,25)]), "obj"
prob += pulp.lpSum([cap[ix]*x[ix] for ix in range(1,25)]) == 6600, "c1"
prob.solve()

print "Status:", LpStatus[prob.status]

for v in prob.variables():
    if v.varValue>0.0001:
        print v.name, "=", v.varValue

print ("objective = %s" % value(prob.objective))

I may have mistyped some coefficients in there, but I'm sure you get my point.

Answer 3

correct with new version pulp for correct errors

---

# Import PuLP modeler functions
from pulp import *

prob = LpProblem("Knapsack_problem", LpMaximize)

cost = [30,18,18,23,18,20,15,16,12,12,25,25,28,35,28,28,25,25,25,28,25,32,32,28,25]
x = LpVariable.dicts('x',range(1,26),lowBound=0,upBound=12,cat=LpInteger)
cap = [150,180,180,230,180,200,150,160,120,120,250,250,280,350,280,280,250,250,250,280,250,320,320,280,250] 
prob += pulp.lpSum([cost[ix]*x[ix] for ix in range(1,25)]), "obj"
prob += pulp.lpSum([cap[ix]*x[ix] for ix in range(1,25)]) == 6600, "c1"
prob.solve()

print ("Status:", LpStatus[prob.status])

for v in prob.variables():
    if v.varValue>0.0001:
        print (v.name, "=", v.varValue)

print ("objective = %s" % value(prob.objective))