The 0-1 Multidimensional Knapsack Problem


This web page is intended to give some additional information as support to the abstract PaperId = 495

"Tabu Search for 0-1 Multidimensional Knapsack Revisited: 
Choosing Internal Heuristics and Fine Tuning of Parameters"

authored by M. Josep Blesa, Lluís Hernàndez and Fatos Xhafa 
submitted to YOR 12 Workshop

Experimental Results

We have tested the Tabu Search Implementation for this problem with standard instances from the literature. For small and medium size instances [Freville, Plateau, 1990] the results are as follows:
 
 
Instance Input File

(problem + 
configuration)
n m known 
optimum
best 
fitness obtained
mean dev. run
iterations
(mean)
t (s)
KNAP15
15 10 4015 4015 4014.1 0 3000 3.6
KNAP20
20 10 6120 6120 6120.0 0 1600 2.5
KNAP28
28 10  12400 12400 12400.0 0 2000 4.1
KNAP39
39 5 10618 10618 10608.0 0 10000 16.8
KNAP50
50 5 16537 16520 16441.0 0.0010 10000 21.3
SENTO1
60 30 7772 7772 7772.0 0 5000 53.5
SENTO2
60 30 8722 8722 8720.6 0 5000 55.5
WEING7
105 2 1095445 1095445 1095319.7 0 4000 13.3
WEING8
105 2 624319 624319 624263.9 0 6000 17.1

We note that for instances of small and medium size we have always found the optimum solution, except for KNAP50.  Interestingly, we have found the optimum solution in almost all the executions except for instance SENTO2 for which the optimum was find in 46% of executions.

For big size instances from OR-Library [Beasley, 1990] our fitness is very close to the best known fitness obtained by other ad hoc implementations (see [CB97]).  These are the results:

Instance Input File

(problem +
configuration)
n m best
known fitness
best 
fitness obtained
mean dev. mean run
iterations
t (s)
OR5x100-00   100 5
24381
22781 22615.1 0.0656 158620.0 600
OR5x250-00 
250 5  59312  55963  55450.8  0.0565  94054.8 900 
OR5x500-00
500 5  120130  112991  112575.3  0.0594  68692.6  1200
OR10x100-00 
100 10 23064 22478 22360.4 0.0254 85629.8 600
OR10x250-00
250 10 59187 56213 55945.6 0.0502 55132.9 900
OR10x500-00 
500 10 117726 111773 111486.7 0.0506 35487.5 1200
OR30x100-00
100 30 21946 21614 21520.7 0.0151 31615.7 600
OR30x250-00
250 30 56693 54711 54534.6 0.0350 15215.1 900
OR30x500-00
500 30 115868 111272 110942.4 0.0397 10459.3 1200
OR5x100-29
100 5 59965 59639 59496.7 0.0054 179516.0 600
OR5x250-29
250 5 154662 153312 153257.2 0.0087 115364.0 900
OR5x500-29
500 5 299904 296939 296079.3 0.0099 81719.4 1200
OR10x100-29
100 10 60633 60629 60518.9 0.0001 110236.2 600
OR10x250-29 
250 10 149704 148342 148121.9 0.0091 68679.3 900
OR10x500-29 
500 10 307014 303943 303642.9 0.0100 44267.8 1200
OR30x100-29
100 30 60603 60432 60292.8 0.0028 37874.5 600
OR30x250-29
250 30 149572 148588 148349.6 0.0066 22437.6 900
OR30x500-29
500 30 300460 298719 298533.4 0.0058 12410.6 1200

The configuration used

Hardware configuration

The executions were done in computers from the BA-Cluster, an heterogeneous cluster of PCs that we are installing in our Department (Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya). The cluster is currently composed by a set of 9 computers:

         ba1.lsi.upc.es
         ba2.lsi.upc.es
         ba3.lsi.upc.es
         ba4.lsi.upc.es
         guernika.lsi.upc.es
         tarkus.lsi.upc.es
         kruja.lsi.upc.es
         alberti.lsi.upc.es
         algenib.lsi.upc.es

By now, all these computers share the same configuration:

         Processor: AMD K6-2 450 MHz
         Main memory: 256 Mb
         Hard Disk: 6 Gb
         Main board: chipset VIA/ALI
         Network adpater: 10/100 Mbps

Computers named ba* only cointain their "box" (no keyboard, no mouse, no screen and no graphic adapter). Computers not named ba* are complete workstations including keyboard, mouse, michrophon, speakers, screen and graphic adapter.

Computers named ba* are interconnected by a dedicated network using a 10/100 switch. guernika, tarkus and kruja could also be connected to this switch but currently are not (we can do that if necessary).

We expect to increase the size of our cluster in the following years with ba*-like computers (the switch can connect 20 more computers!).
 

Execution configuration

The experiments have been done with different configurations mainly depending on the size of the problem. A configuration consist of a set of values for the setup parameters (see below).  The concrete values used for each instance can be obtained by retrieving the complete input file (2nd column of the tables). These input files contain the problem and the setup parameters (see below).

Fine Tuning of Parameters

Here we refer only to two important internal heuristics for Tabu Search  method, namely the  intensification and diversification. A detailed explanation will be given in the full version of the paper.
 

Intensification & Equality of solutions

Initially, the search is instensified if the same solution is reached at least max_repetitions times. We found that if the equality of solutions is defined strictly the intensification is never activated (due to the heuristic used for the neighborhood exploration). So the equality has been relaxed.

We introduce the concept of distance between solutions that measures the number of items whose values are different in a solution compared with another solution.  Since a solution is implemented as a binary array of size n (the number of items) it is clear that this distance is the Hamming distance. So we have redefined the "equality" between two solutions in terms of Hamming distance and consider two solutions "equal" if they difer in a very small number of items.

For the number of differences between two given solutions (i.e. the Hamming distance) we have observed this behavior:
 


The figure below compares the growth of both expressions for k=0.05 (in the first one) and k=0.1 (in the second one).

Our diversification strategy includes two forms: soft diversification (explained below) and strong diversification (this is essentially an escape mecanism that permits exploring in a new region of the solution space).
 

Soft diversification & history_rep

The parameter history_rep is a percentage used to decide if an item has been incorporated many times to the solution in process during the search. This parameter has an important influence when diversifying softly.

We initially used a constant value (not a percentage) for the history_rep and compared it with all the elements of the array HISTORY (as [NF96] do) but drawbacks were found, so we considered it as a percentage.  This parameters has become adaptable since it gets a proportional value (wrt the elements of the array HISTORY) each iteration of the diversification stage.

rep = (history_rep / 100) * max { HISTORY[j],  j=1..n }

As we can see in the figure below, the best results are obtained when the value of history_rep is large (that means "more softness" in the soft diversification).