| ||||||||||||
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
- V is a positive integer
- The volumes, vj, j=1,2,...,n, are strictly positive integers
The method we use to solve this problem here is branch and bound (BB). Here is a rough sketch of how it works:
- Step 0: Pre-processing
At this stage we try to reduce the size of the problem by eliminating bad items and/or reducing the size of the knapsack (V). We also rearrange the items in decreasing order of their densities (w[j]/v[j]). - Step 1: Initialization
We find a "good" feasible solution to the problem by filling the knapsack with as many items of type 1 as possible, then as many items of type 2 as possible, etc. - Step 2: Reduction move
We delete one item from the knapsack. - Step 3: Expansion move
We attempt to improve the current selection by utilising items from the "tail" of the process.
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:
- Quickly compute an upper bound on the possible contribution from the tail of the current solution using the Greedy Rule and ignoring the integrality constraints.
- If the upper bound is better than the current optimal solution expand the current solution using the Greedy Rule. If it is not, go to Step 2 and apply a reduction to the current feasible solution.
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).
- Step 0: Preprocessing
We re-arrange the items in decreasing order of their densities. Since they are already arranged this way, there is no need to change their order. - Step 1: Initialization
In accordance with the Greedy Rule, we select 2 items of type 1, 0 items of type 2 and 0 items of type 3. Thus, the initial feasible solution is x=(2,0,0), whose total weight is W = 22. - Step 2: Reduction
The last non-zero component of x is 1, so we set k=1, and delete one item of type 1 from x. This yileds the feasible solution x=(1,0,0). - Step 3: Expansion
Given the current solution x=(1,0,0) and k=1, we have 10-4=6 units of volume at our disposal. We apply the Greedy Rule to compute an upper bound for the optimal weight based on x. In other words, we select as many items of type 2 t(hiagnoring the integrality constraints) that can fit into a knapsack of volume 6. Thus, we select 1.2 item of type 2, so the total weight is 11+ 12x1.2 = 25.4. This is better than the current optimal weight, so we use the Greedy Rule (subject to the integrality constraints) to generate a feasibe solution. the result is x=(1,1,0). - Step 2: Reduction
The last non-zero component of x is k=2. So we delete one item of type 2. The feasible solution is thus x=(1,0,0). - Step 3: Expansion Given the current feasible solution x=(1,0,0) and k=2, we do the best we can with the remaining volume (6 units) utlising the tail of the process (j>k). In other words, we select 2 items of type 3. This generate the feasible solution =x(1,0,2), yileding a totla weight W=25. This is better than the previous best solution.
- Step 2: Reduction
The last non-zero component of x is k=3. So we delete one item of type 3. This leaves us with the feasible solution x=(1,0,1). - Step 3: Expansion
Since we are at the last pile (k=n) we cannot expand. - Step 2: Reduction
The last non-zero component of x is k=3. So we delete one item of type 3. This leaves us with the feasible solution x=(1,0,0). - Step 3: Expansion
Since we are at the last pile (k=n) we cannot expand. - Step 2: Reduction
The last non-zero component of x is k=1. So we delete one item of type 1. This leaves us with the feasible solution x=(0,0,0). - Step 3: Expansion
We do the best we can with the remaining volume (10 units) as prescribed by the Greedy Rule. This yields x=(0,2,0). - Step 2: Reduction
The last non-zero component of x is k=2. So we delete one item of type 2. This leaves us with the feasible solution x=(0,1,0). - Step 3: Expansion
We do the best we can with the remaining volume (10 - 5 = 5 units). This yields x=(0,1,1). - Step 2: Reduction
The last non-zero component of x is k=3. So we delete one item of type 3. This leaves us with the feasible solution x=(0,1,0). - Step 3: Expansion
Since we are at the last pile (k=n) we cannot expand. - Step 2: Reduction
The last non-zero component of x is k=2. So we delete one item of type 2. This leaves us with the feasible solution x=(0,0,0). - Step 3: Expansion
k=2, so we do the best we can with items of type 3. This yields x=(0,0,3). - Step 2: Reduction
The last non-zero component of x is k=3. So we delete one item of type 3. This leaves us with the feasible solution x=(0,0,2). - Step 3: Expansion
Since we are at the last pile (k=n) we cannot expand. - Step 2: Reduction
The last non-zero component of x is k=3. So we delete one item of type 3. This leaves us with the feasible solution x=(0,0,1). - Step 3: Expansion
Since we are at the last pile (k=n) we cannot expand. - Step 2: Reduction
The last non-zero component of x is k=3. So we delete one item of type 3. This leaves us with the feasible solution x=(0,0,0). - Step 3: Expansion
Since we are at the last pile (k=n) we cannot expand. - Step 2: Reduction
x=(0,0,0) so we stop.
Our records show that the best solution we generated is x=(1,0,2), hence this is an optimal solution.
Remark:
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
|
|
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.
Email: m.sniedovich@ms.unimelb.edu.au