The Unbounded Knapsack Problem

z* := max z = w1x1 + w2x2 + ... + wnxn
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 (wj) and volume (vj). The objective is to determine how many items from each pile (xj) 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).

The symbol ":=" is used to denote a definition.

It is very convenient to assume at the outset that

The method we use to solve this problem here is branch and bound (BB). Here is a rough sketch of how it works:

The process terminates when, in Step 2, no further reduction is possible

To describe the details of Step 2 and Step 3 let us consider a typical feasible solution to the problem, call it x=(x(1),x(2),...,x(n)). Let k denote the largest index j such that x(j) > 0. For example, for x=(0,1,2,0,6,0,0), we have k=5. If x is the current solution, then the reduction step simply involves deletion of one item of type k. Thus, if we apply the reduction step to x=(0,1,2,0,6,0,0), we obtain the feasible solution y=(0,1,2,0,5,0,0).

Admittedly, this is really a very simple step.

Step 3 - the expansion step - is much more involved. It consists of two sub-steps:

In case you are in doubt, yes, the Greedy Rule is the rule according to which the items are selected according to their densities (in decreasing order).

Consier as an example the case where n=3, V=10, w=(11,12,7), v=(4,5,3).

Our records show that the best solution we generated is x=(1,0,2), hence this is an optimal solution.

Since the weights {w(j)} are positive, reductions at the last stage (k=n) cannot improve the current optimal solution. Thus, to speed up the process, x=(?,?,?, ... , M) can be reduced directly to x=(?,?,?,...,0).

Would it be nice to have a faciltity to do this kind of boring coputation for us so that we can relax and ..... go fishing instead!

Well, here it is!

You are reminded though that acquiring OR/MS skills is not all about fishing, dancing, skating and surfing!

The current module is basically doing everything for you so you can really completely relax. However, we plan to enhance the module so that it will be completely controlled by you, the user. When this feature will be ready you'll have to give up your fishing and spend time mastering the details of this method.

Contributed by

© The University of Melbourne 1994-2000.
Disclaimer and Copyright Information.
Conditions of use.
Date created: January 15, 2000
Date last modified: February 15, 2000
Authorised by: Moshe Sniedovich
Maintained by: Moshe Sniedovich, Department of Mathematics and Statistics.