---

Introduction to the Knapsack Problem

---

This problem is a truly OR celebrity. Several factors have contributed to its prominent status in OR circles. Firstly, it represents a very large number of real-world problems. Secondly, it provides very good teaching material.

The objective of this discussion is to briefly discuss the versions of the problems we shall consider in our Knapsack Module and the two solution methods we shall use.

As we indicated at the outset, there are numerous versions to this problem. We shall consider only three:

• Unbounded Problem
• Bounded Problem
• 0-1 Problem

The two solution methods we shall use are:

• Branch and Bound (BB)
• Dynamic Programming (DP)

The main goal of this broad overview is to introduce the notation and terminology that we shall subsequently use in the sub-modules and to motivate the strucutre of the user-interface to computational facilities.

---

Unbounded Problem

---

The main feature of this version of the problem is that there are infinitely many items of each type (pile). Thus, the problem can be stated mathematically as follows:

z* := max z = w1x1 + w2x2 + ... + wnxn s.t. v1x1 + v2x2 + ... + vnxn <= V x1,x2, ... ,xn in {0,1,2,3, ... }

In words, we have a knpsack of volume V and n piles (j=1,2,...,n) of items. Each pile contains infinitely many identical items having the same weight (w_j) and volume (v_j). The objective is to determine how many items from each pile (x_j) should be placed in the knapsack so as to maximize the total weight of the knpsack without exceeding the total volume of the knapsack (V).

Incidentally, we use the symbol ":=" to denote a definition.

It is very convenient to assume at the outset that

• V is a positive integer
• The volumes, v_j, j=1,2,...,n, are positive integers

Note that the weights are allowed to be non-integers, in fact they are also allowed to be negative. If you are concerned about the idea that weights of items are allowed to be negative, then ... relax. We do not suggest that such items exist. The point is, however, that the Knapsack Problem represents many real-life problems that are not at all "Knapsack Problems" as such. We use the term "Knapsack Problem" as shorthand for the above mathematical model and in that context it is perfectly OK to allow the w_js to be negative.

Last but not least, sometime we shall refer to the piles as types, and talk about "an item of type j " rather than "an items from pile j" .

---

Bounded Problem

---

This version of the problem is identical to the Unbounded Problem except that there might be bounds (lower and/or upper) on the size of each pile.

Thus, the mathematical formulation of this version of the problem is a s follows:

z* := max z = w1x1 + w2x2 + ... + wnxn s.t. v1x1 + v2x2 + ... + vnxn <= V x1,x2, ... ,xn in {0,1,2,3, ... } Lj <= xj <= Uj, j = in {1,2,3, ... ,n }

We assume that all the bounds are non-negative integers and that obviously

L_j <= U_j, for all j = in {1,2,3, ... ,n }

Observe that given that the volume of the knapsack is equal to V, it is sensible to restrict the range of values of the lower bounds (L_j) to ensure that the problem is feasible. That is, it makes sense to assume that

L_j <= V/v_j, for all j = in {1,2,3, ... ,n }

for otherwise the problem is not feasible as the knapsack is too small.

By the same token, it make sense to assume that

U_j <= V/v_j, for all j = in {1,2,3, ... ,n }

for otherwise at least one of the upper bounds is superfluous.

Of course, our main concerned is with the upper bounds, as the lower bounds can be easily handled by setting them all to zero and adjusting the value of V, namely replacing V by

V - (L_j + L_j + ... + L_n)

As we indicated already then, all in all this version of the problem is very similar to the Unbounded Problem.

---

0-1 Problem

---

This is a special instance of the Bounded Problem in which all the lower bounds are equal to zero and all the upper bounds are equal to 1. Thus, the mathematical formulation of this version of the problem is as follows:

z* := max z = w1x1 + w2x2 + ... + wnxn s.t. v1x1 + v2x2 + ... + vnxn <= V x1,x2, ... ,xn in {0,1}

Observe that this version of the problem can be described in words as follows:

There are n items, j=1,...,n, each with a weight w_j and a volume v_j. Given a knapsack of volume V, what items should be placed in the knapsack so as to maximize the total weight of the knapack?

In other words, the problem involves a selection of a sub-set of a given set of distinct items.

As a modelling exercise you may wish to show that any one of the other two versions of the problem we considered above can be cast as a 1-0 Problem - provided, of course, that we do not require the items to be distinct.

---

Branch and Bound Method

---

This implicit enumeration method capitalises on the fact that if the integrality constraint is relaxed from the formulation of the Knapsack Problem, then two things happen:

• The (relaxed) problem is very easy to solve
• The optimal value of the objective function of the relaxed problem is an upper bound of the optimal value of the objective function of the original problem.

For example, consider the relaxed problem induced by the Unbounded Problem, namely

zo := max z = w1x1 + w2x2 + ... + wnxn s.t. v1x1 + v2x2 + ... + vnxn <= V x1,x2, ... ,xn >= 0

Then clearly the optimal solution is to fill the knapsack with items whose specific weight is the largest. The optimal solution is thus:

x_j = 0 , for all j except k
x_k = V/v_k

where k is any pile such that

w_k/ v_k = max { w_j/ v_j: j =1,2,...,n}

This implies that

z^o = Vw_k/ v_k >= z*

Roughly speaking, the branch and bound method conducts an implicit enumeration of all the feasible solution to the knapsack problem except that it discards partial solutions as soon as it can be established that they cannot lead to a complete solution that is optimal with respect to the original (unrelaxed) problem. In doing so it relies on upper bounds of the type we discussed above on the objective function of the original problem.

---

Dynamic Programming

---

This method handles the Knapsack Problem by solving a functional equation relating optimal solutions to sub-problems of the original problem.

For the benefit of readers who are not familiar with DP we note that a typical dynamic programming functional equation for the Unbounded Knapsack Problem will look like this:

f(s) = 0 , for all s < w_p
f(s) = max {w_j + f(s-v_j): v_j <= s, j=1,2,...,n}, s >= w_p

where p is an item type of the smallest volume.

Don't panic (yet) if this looks like magic to you. There will be a detailed explanation for this result in the module dealing with the respective sub-module.

And if you cannot sleep at night because you can't wait for the explanation, you can ready something short about this beauty most introductory books on Operations Research and Mathematical Probramming.

---

Generalisations

---

There are a number of generalisations to the Knapsack problem that can be easily taken care of by either DP and/or BB.We mention the following:

• Minimization rather than maximization.
• "=" rather than "<=" functional constraint.

---

User Interface

---

The basic input data that must be provided by the user about the knapsack problem is as follows:

Data Description Specifications V Volume of knapsack Positive Integer n Number of piles Positive Integer vj Volume of an item of type j Positive Integer wj Weight of an item of type j Real number opt Optimization criterion Either min or max Constraint Type of functional constraint Either "<=" or "=" Lj Lower bound on xj Non-negative Integer Uj Upper bound on xj Positive Integer Integer

The last two rows pertain only to the Unbounded Problem.

Ultimately, the input form for the overall module will be designed to take care of all these details. It will also enable the users to specify the solution method to be used, namely BB or DP.