2.2 Integer formulation of the knapsack problem:

Consider again, the knapsack problem. Assume now that we can acquire multiple items of the same type. In this new formulation, \(x_{i}\) is now an integer variable instead of a binary variable. One way to formulate this problem is as follows:

\[max_{q,x} \sum _{i \in A} v_{i}x_{i}\]

\[s.t \sum _{i \in A} w_{i}x_{i} \leq W_{max}\]

\[x_{i} = \sum ^{N} _{j=0}jq_{i,j} \;\;\;\;\;\;\; \forall i \in A\]

\[0 \leq x \leq N\]

\[q_{i,j} \in \{0,1\} \;\;\;\; \forall i \in A, j \in \{0..N\}\]

Below we implement this new formulation and solve. Is the solution surprising?

import pyomo.environ as pyo

A = ['hammer', 'wrench', 'screwdriver', 'towel']
b = {'hammer':8, 'wrench':3, 'screwdriver':6, 'towel':11}
w = {'hammer':5, 'wrench':7, 'screwdriver':4, 'towel':3}
W_max = 14
N = range(6) # create a list from 0-5

model = pyo.ConcreteModel()
model.x = pyo.Var( A )
model.q = pyo.Var( A, N, within=pyo.Binary )

def obj_rule(m):
    return sum( b[i]*m.x[i] for i in A )
model.obj = pyo.Objective(rule=obj_rule, sense = pyo.maximize )

def weight_con_rule(m):
    return sum( w[i]*m.x[i] for i in A ) <= W_max
model.weight_con = pyo.Constraint(rule=weight_con_rule)

def x_integer_rule(m, i):
    return m.x[i] == sum( j*m.q[i,j] for j in N )
model.x_integer = pyo.Constraint(A, rule=x_integer_rule)

opt = pyo.SolverFactory('glpk')
result_obj = opt.solve(model)

total_weight = sum( w[i]*pyo.value(model.x[i]) for i in A )
print('Total Weight:', total_weight)
print('Total Benefit:', pyo.value(model.obj))

print('%12s %12s' % ('Item', '# Selected'))
print('=========================')
for i in A:
    print('%12s %12s' % (i, pyo.value(model.x[i])))
print('-------------------------')

Total Weight: 12.0
Total Benefit: 44.0
        Item   # Selected
=========================
      hammer          0.0
      wrench          0.0
 screwdriver          0.0
       towel          4.0
-------------------------