Knapsack Optimization
Objective: Maximize the value of items that can fit into a knapsack without exceeding a maximum weight constraint.
There are 4 items available to be placed in a knapsack: a towel, hammer, wrench, and screwdriver. The value and weight of the items are listed in the table below.

The purpose of the knapsack problem is to select which items to fit into the bag without exceeding a weight limit of what can be carried. We solve the problem with an integer programming solver (APOPT) by setting up each item as a binary variable (0 or 1). A zero (0) is a decision to not place the item in the knapsack while a one (1) is a decision to include it. More generally, suppose there are `n` items with values `v_1, \ldots, v_n` and weights `w_1, \ldots, w_n` with a total weight limit of the sack `W=14`. The decision variables are `x_1, \ldots, x_n` that can be 0 or 1. The following optimization formulation represents this problem as an integer program:
$$\max \sum _{i=1}^{n} v_{i} x_{i}$$
$$\textrm{subject to} \sum _{i=1}^{n} w_{i} x_{i}\leq W$$
$$x_{i}\in \{0,1\}$$
Python GEKKO Solution
y = ['towel','hammer','wrench','screwdriver']
v = [11,8,3,6]
w = [3,5,7,4]
items = len(y)
# Create model
m = GEKKO()
# Variables
x = m.Array(m.Var,len(y),lb=0,ub=1,integer=True)
# Objective
m.Obj(sum(v[i]*x[i] for i in range(items)))
# Constraint
limit = 14
m.Equation(sum([w[i]*x[i] for i in range(items)]) <= limit)
# Optimize with APOPT
m.options.SOLVER = 1
m.solve()
# Print the value of the variables at the optimum
for i in range(items):
print("%s = %f" % (y[i], x[i].value[0]))
# Print the value of the objective
print("Objective = %f" % (m.options.objfcnval))
m.open_folder()
comments powered by Disqus