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 
accepted at YOR 12 Workshop


We have parallelized the internal part of the skeleton (that implementing the Tabu Search method independently of the problem to solve) using different parallelization strategies.  Because the parallelized part is hidden to the user, he/she can obtain a parallel execution of his/her sequential instantiation without any additional effort.  Therefore, using our sequential implementation of the Knapsack we have obtained a parallel implementation for the problem. The parallel executions had been run over 2, 4 and 8 processors of our PC-cluster.

The first strategy studied is the simplest form of parallelism: more than one executions of the method running at the same time in different processors without interacting.  We are studying more complicated parallelization strategies but, by now, we have only results for the Independent Runs strategy.

Experimental Results for the Direct Movement Implementation

In the experiments done we have fixed a maximum execution time and we have varied the number of independent runs (processors).  Some instances of the OR-Library had been used as input of our parallel implementation (OR5x100-00, OR5x100-29, OR10x100-00, OR10x100-29, OR30x100-00, OR30x100-29, OR5x250-00, OR5x250-29, OR10x250-00, OR10x250-29, OR30x250-00, OR30x250-29,  OR5x500-00, OR5x500-29, OR10x500-00, OR10x500-29, OR30x500-00, OR30x500-29). The bigger the instance is, the larger is the maximum execution time allowed.  It's interesting to note here that, in general, the experimental results obtained from the parallel implementation improve upon the sequential ones.

Independent Runs Model:

Instances computed with maximum running time (max_time) = 600 s.


       IR strategy with  2  Independent parallel runs (processors) :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x100-00
100
5
24381
24083
23981.6
0.0122
177222.0
606.3
OR5x100-29
100
5
59965
59646
59497.0
0.0053
247579.4
606.4
OR10x100-00
100
10
 23064
22557
22337.2
0.0220
114937.4
607.4
OR10x100-29
100
10
60633
60626
60489.2
0.0001
159064.8
607.6
OR30x100-00
100
30
21946
21614
21546.8
0.0151
44897.0
609.6
OR30x100-29
100
30
60603
60503
60341.8
0.0017
57533.4
609.4
IR strategy with  4  Independent parallel runs (processors) :
Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x100-00
100
5
24381
24318
24205.4
0.0025
526785.0
610.1
OR5x100-29
100
5
59965
59620
59458.0
0.0058
729686.0
610.3
OR10x100-00
100
10
 23064
22644
22414.4
0.0182
343089.6
611.2
OR10x100-29
100
10
60633
60629
60603.6
0.0001
453284.6
611.6
OR30x100-00
100
30
21946
21651
21595.2
0.0134
129800.4
614.0
OR30x100-29
100
30
60603
60503
60420.4
0.0017
171800.2
613.1

       IR strategy with  8  Independent parallel runs (processors) :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x100-00
100
5
24381
24211
24162.2
0.0070
1192054.6
619.8
OR5x100-29
100
5
59965
59667
59533.6
0.0050
1633099.8
620.8
OR10x100-00
100
10
 23064
22478
22419.4
0.0254
753246.6
630.2
OR10x100-29
100
10
60633
60629
60627.2
0.0001
1001095.8
625.8
OR30x100-00
100
30
21946
21649
21623.0
0.0135
275664.4
624.9
OR30x100-29
100
30
60603
60503
60483.8
0.0017
364593.2
624.3

 

Instances computed with maximum running time (max_time) = 900 s.


       IR strategy with  2  Independent parallel runs (processors) :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x250-00
250
5
59312
56380
55681.6
0.0494
119641.6
908.0
OR5x250-29
250
5
154662
153526
153227.6
0.0073
151808.6
908.2
OR10x250-00
250
10
 59187
56414
56136.6
0.0469
75015.2
909.5
OR10x250-29
250
10
149704
148252
147977.2
0.0097
96986.0
909.3
OR30x250-00
250
30
56693
54578
54533.0
0.0373
24314.4
915.7
OR30x250-29
250
30
149572
148357
148232.0
0.0081
34610.0
915.6

       IR strategy with  4  Independent parallel runs (processors) :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x250-00
250
5
59312
56980
56290.4
0.0393
359956.0
912.0
OR5x250-29
250
5
154662
153684
153483.8
0.0063
449184.0
911.1
OR10x250-00
250
10
 59187
56727
56416.4
0.0416
224706.6
915.6
OR10x250-29
250
10
149704
148280
148083.2
0.0095
286595.6
914.7
OR30x250-00
250
30
56693
54792
54715.2
0.0335
70720.6
921.0
OR30x250-29
250
30
149572
148621
148427.8
0.0064
100949.4
919.6

       IR strategy with  8  Independent parallel runs (processors) :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x250-00
250
5
59312
56759
56490
0.0430
804849.0
939.1
OR5x250-29
250
5
154662
         
OR10x250-00
250
10
 59187
56664
56405.8
0.0426
490034.4
926.0
OR10x250-29
250
10
149704
148414
148257.0
0.0086
623402.4
932.2
OR30x250-00
250
30
56693
54855
54762.4
0.0324
151330.6
936.5
OR30x250-29
250
30
149572
148617
148482.2
0.0064
222286.4
931.4

 

Instances computed with maximum running time (max_time) = 1200 s.


        IR strategy with 2  Independent parallel runs (processors) :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x500-00
500
5
120130
113326
112776.6
0.0566
71190.0
1215.3
OR5x500-29
500
5
299904
297679
297074.4
0.0074
86169.8
1210.4
OR10x500-00
500
10
 117726
111974
111193.4
0.0489
40109.6
1214.2
OR10x500-29
500
10
307014
303614
303487.6
0.0111
53254.8
1213.9
OR30x500-00
500
30
115868
111358
111081.8
0.0389
10612.4
1226.6
OR30x500-29
500
30
300460
298569
298463.6
0.0063
16284.0
1228.8

       IR strategy with  4  Independent parallel runs (processors) :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x500-00
500
5
120130
114741
114187.4
0.0449
242854.0
1212.6
OR5x500-29
500
5
299904
297383
297111.4
0.0084
298442.6
1212.9
OR10x500-00
500
10
 117726
112199
111742.6
0.0470
144402.8
1221.1
OR10x500-29
500
10
307014
304354
303823.8
0.0087
185546.6
1217.5
OR30x500-00
500
30
115868
111648
111118.6
0.0364
42970.4
1228.8
OR30x500-29
500
30
300460
298753
298612.0
0.0057
61519.8
1229.3

       IR strategy with  8  Independent parallel runs (processors) :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x500-00
500
5
120130
114469
114070.0
0.0471
526232.0
1348.8
OR5x500-29
500
5
299904
297707
297453.8
0.0073
644637.2
1229.1
OR10x500-00
500
10
 117726
112983
112254.0
0.0403
326128.0
1243.2
OR10x500-29
500
10
307014
304122
303849.2
0.0094
416856.2
1232.3
OR30x500-00
500
30
115868
111786
111464.2
0.0352
87063.6
1248.9
OR30x500-29
500
30
300460
298746
298687.6
0.0057
129835.6
1241.3

 

Experimental Results for the Combinatorial Movement Implementation

We have also implemented the movement and the neighborhood exploration in a combinatorial way.  Using this implementation a broader exploration is performed and the chosen movements usually lead to better solutions that the ones obtained with the direct implementation.

The combinatorial movement is defined as a pair of items: one to be dropped and one to be added. The combinatorial neighborhood is defined as all the possible combinations of selecting an element to be dropped and an element to be added.
 

Independent Runs Model:

Instances computed with maximum running time (max_time) = 600 s.


       IR strategy with  2  Independent parallel runs (processors) :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x100-00
100
5
24381
 24381
24075.2
0
9112.0
600.7 
OR5x100-29
100
5
59965
 59931
59728.0
0.0006 
5562.6 
600.7 
OR10x100-00
100
10
 23064
 22978
22851.6 
0.0037 
 10430.6
600.9 
OR10x100-29
100
10
60633
 60633
60590.0
6994.2 
601.5 
OR30x100-00
100
30
21946
 21829
 21664.0
0.0053 
6749.4 
601.0 
OR30x100-29
100
30
60603
60472
60381.6 
0.0022 
4580.0 
601.9 
IR strategy with  4  Independent parallel runs (processors) :
Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x100-00
100
5
24381
 24329
24244.6 
0.0021
25710.0 
601.0 
OR5x100-29
100
5
59965
 59955
59919.4 
0.0002
24355.2 
600.6 
OR10x100-00
100
10
 23064
23011
22931.0
0.0023
23355.8 
601.1 
OR10x100-29
100
10
60633
 60633
60553.6 
18109.0 
601.7 
OR30x100-00
100
30
21946
 21946
21780.2 
17297.4 
601.3 
OR30x100-29
100
30
60603
 60603
60410.8 
11961.6 
602.1

Instances computed with maximum running time (max_time) = 900 s.


       IR strategy with  2  Independent parallel runs (processors) :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x250-00
250
5
59312
 58610
58492.0 
0.0118 
2163.0 
906.4 
OR5x250-29
250
5
154662
 154437
154154.6 
0.0015 
1452.8 
904.4 
OR10x250-00
250
10
 59187
 58353
58005.2 
0.0141 
1837.0 
902.2 
OR10x250-29
250
10
149704
 148499
148056.2 
0.0080 
822.0 
909.0 
OR30x250-00
250
30
56693
 55567
 55501.8
0.0199 
2016.8 
903.1 
OR30x250-29
250
30
149572
148710
148489.0 
0.0058 
555.2 
913.5 

       IR strategy with  4  Independent parallel runs (processors) :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x250-00
250
5
59312
 58908
58636.8 
0.0068 
6784.8 
904.3 
OR5x250-29
250
5
154662
154446
154132.3 
0.0014 
3362.8 
908.0 
OR10x250-00
250
10
 59187
 58090
58015.6 
0.0185 
5204.4 
907.3 
OR10x250-29
250
10
149704
 149009
148767.0 
0.0046 
2782.6 
915.1 
OR30x250-00
250
30
56693
 55909
 55648.2
0.0138 
4404.8 
908.2 
OR30x250-29
250
30
149572
 148901
148621.0 
0.0045 
1326.8 
934.3 

Instances computed with maximum running time (max_time) = 1200 s.


        IR strategy with 2  Independent parallel runs (processors) :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x500-00
500
5
120130
 116958
114851.2 
0.0264 
353.6 
1208.8 
OR5x500-29
500
5
299904
 295678
294292.4 
0.0141 
246.6 
1220.0 
OR10x500-00
500
10
 117726
 115191
112998.6 
0.0215 
609.6 
1210.6 
OR10x500-29
500
10
307014
 303476
303422.4 
0.0115
258.2 
1251.8 
OR30x500-00
500
30
115868
112863
111845.0 
0.0259 
729.2 
1201.2 
OR30x500-29
500
30
300460
 298450
297875.8 
0.0067 
189.4 
1231.7 

       IR strategy with  4  Independent parallel runs (processors) :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x500-00
500
5
120130
 116561
113983.6 
0.0297 
1219.4 
1244.7 
OR5x500-29
500
5
299904
 296956
295761.0 
 0.0098
813.0 
1265.8 
OR10x500-00
500
10
 117726
 115241
114707.0 
0.0211 
1740.0 
1225.5 
OR10x500-29
500
10
307014
 302425
302196.2 
0.0149 
606.0 
1205.2 
OR30x500-00
500
30
115868
 113453
112673.2 
0.0208 
1945.0 
1226.5 
OR30x500-29
500
30
300460
 298193
297565.0 
0.0075 
487.0 
1277.4 

 

Master-Slave Model:

Instances computed with maximum running time (max_time) = 600 s.

       M-S strategy with  p=2 :
 
Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x100-00
100
5
24381
 24220
24109.2 
0.0066 
5459.6 
607.1 
OR5x100-29
100
5
59965
 59955
59878.2 
0.0002 
5691.8 
606.5 
OR10x100-00
100
10
 23064
 23055
22931.4 
0.0004 
4926.0 
607.1 
OR10x100-29
100
10
60633
 60629
60579.8 
0.0001 
3970.6 
608.3 
OR30x100-00
100
30
21946
 21707
21629.4 
0.0109 
2240.0 
612.0 
OR30x100-29
100
30
60603
 60327
60158.0 
0.0046 
1700.2 
612.6

       M-S strategy with  p=4 :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x100-00
100
5
24381
 24329
24232.4 
0.0021 
4169.8 
609.8 
OR5x100-29
100
5
59965
59846 
59738.6 
0.0020 
3294.8 
610.7 
OR10x100-00
100
10
 23064
 22966
22833.4 
0.0042 
3177.4 
611.8 
OR10x100-29
100
10
60633
 60633
60590.2 
2770.8 
611.6 
OR30x100-00
100
30
21946
21662 
21620.8 
0.0129 
1337.8 
616.0 
OR30x100-29
100
30
60603
 60351
60160.4 
0.0042 
1104.4 
614.4 

       M-S strategy with  p=8 :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x100-00
100
5
24381
 24282
24052.2 
0.0041 
1838.0 
618.8 
OR5x100-29
100
5
59965
 59896
59792.6 
0.0012 
1723.0 
620.4 
OR10x100-00
100
10
 23064
 22717
22670.0 
0.0150 
1079.8 
622.5 
OR10x100-29
100
10
60633
 60629
60507.4 
0.0001 
1040.4 
619.5 
OR30x100-00
100
30
21946
 21616
21493.8 
0.0150 
430.4 
626.4 
OR30x100-29
100
30
60603
 60123
60072.2 
0.0079 
387.2 
629.0 

 

Instances computed with maximum running time (max_time) = 900 s.

       M-S strategy with  p=2 :
 
Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x250-00
250
5
59312
 58389
58282.2 
0.0156 
1711.8 
910.2 
OR5x250-29
250
5
154662
 154398
154199.6 
0.0017 
1101.4 
912.0 
OR10x250-00
250
10
 59187
 58176
58097.6 
0.0171 
1431.0 
912.4 
OR10x250-29
250
10
149704
 148532
148140.0 
0.0078 
674.8 
923.0 
OR30x250-00
250
30
56693
55642 
55285.8 
0.0185 
797.0 
921.5 
OR30x250-29
250
30
149572
148934 
148416.2 
0.0043 
424.6 
918.7 

       M-S strategy with  p=4 :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x250-00
250
5
59312
58736 
58318.6 
0.0097 
1389.4 
915.6 
OR5x250-29
250
5
154662
154315 
153862.0
0.0022 
838.6 
920.7 
OR10x250-00
250
10
 59187
57847 
57606.6 
0.0226 
1141.6 
917.6 
OR10x250-29
250
10
149704
148426 
148237.2 
0.0085 
625.6 
928.0 
OR30x250-00
250
30
56693
56037 
55174.6 
0.0116 
501.2 
927.3 
OR30x250-29
250
30
149572
148862 
148598.8 
0.0047 
334.2 
937.8 

       M-S strategy with  p=8 :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x250-00
250
5
59312
58660 
58274.2 
0.0110 
771.0 
921.5 
OR5x250-29
250
5
154662
154105 
153643.0 
0.0036 
554.8 
928.7 
OR10x250-00
250
10
 59187
57674 
57227.4 
0.0256 
492.4 
929.1 
OR10x250-29
250
10
149704
148151 
147805.2 
0.0104 
368.2 
937.7 
OR30x250-00
250
30
56693
55323 
54937.8 
0.0242 
234.5 
937.5 
OR30x250-29
250
30
149572
148582 
148259.4 
0.0066 
199.0 
960.2 

Instances computed with maximum running time (max_time) = 1200 s.

       M-S strategy with  p=2 :
 
Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x500-00
500
5
120130
116025 
115367.4 
0.0642 
373.2 
1218.9 
OR5x500-29
500
5
299904
295162 
294688.0 
0.0158 
233.2 
1229.8 
OR10x500-00
500
10
 117726
115087 
113584.4 
0.0224 
592.2 
1237.5 
OR10x500-29
500
10
307014
305051 
303728.2 
0.0064 
274.4 
1235.9 
OR30x500-00
500
30
115868
112620 
111334.0 
0.0280 
380.2 
1227.9 
OR30x500-29
500
30
300460
298211 
297746.6 
0.0075 
181.8 
1238.9 

       M-S strategy with  p=4 :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x500-00
500
5
120130
116550 
114838.4 
0.0298 
378.4 
1229.8 
OR5x500-29
500
5
299904
296891 
293510.8 
0.0100 
234.6 
1215.7 
OR10x500-00
500
10
 117726
114635 
113513.6 
0.0263 
436.6 
1228.2 
OR10x500-29
500
10
307014
303690 
303179.0 
0.0108 
215.2 
1235.3 
OR30x500-00
500
30
115868
111340 
110791.6 
0.0391 
319.4 
1241.2 
OR30x500-29
500
30
300460
298683 
297912.2 
0.0059 
146.4 
1294.9

       M-S strategy with  p=8  :
 

Instance
n
m
known 
optimum
best 
fitness obtained
mean
dev.
run
iterations
(mean)
t (s)
OR5x500-00
500
5
120130
115552 
112096.8 
0.0381 
281.4 
1233.3 
OR5x500-29
500
5
299904
295432 
293429.4 
0.0149 
191.0 
1272.5 
OR10x500-00
500
10
 117726
114161 
113312.2 
0.0303 
253.6 
1224.6 
OR10x500-29
500
10
307014
303469 
303322.6 
0.0115 
187.2 
1272.8 
OR30x500-00
500
30
115868
110133 
109422.2 
0.0495 
141.0 
1240.0 
OR30x500-29
500
30
300460
297681 
297614.4 
0.0092 
97.6 
1289.4