Main

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.

TowelHammerWrenchScrewdriver
Item Value (vi) 11 8 3 6
Item Weight (wi) 3 5 7 4

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

from gekko import GEKKO

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