Article:

Alberto Caprara and Paolo Toth. Lower bounds and algorithms for the 2-dimensional vector packing problem. Discrete Applied Mathematics, 111:231-261, 2001

Instances defined:

Capara-Toth

Instances used:

Spieksma

Results:

The exact algorithms were coded in FORTRAN 77 and executed on Digital DECStation 5000/240 CPU. The Classes 1-3 are taken form [Spieksma, 1994], while the other classes are created by Caprara and Toth. The execution time of the algorithms by Caprara and Toth is adjusted to the computation time of the machine used by [Spieksma, 1994].

Class
n
Spieksma
BB_1
BB_2
BB_3
BP
Hybrid
time
 # opt
time
 # opt
time
 # opt
time
 # opt
time
 # opt
time
 # opt
1
25
0.335
10
0.243
10
33.297
10
0.310
10
7.668
10
0.310
10
1
50
794.097
7
996.711
6
1051.221
8
30.452
10
129.503
10
30.452
10
1
100
-
0
1.883
2
10.809
2
109.727
8
1579.792
10
678.723
10
1
200
-
0
-
0
-
0
844.437
5
19481.840
9
15437.271
10
2
25
0.317
10
0.150
10
0.150
10
0.150
10
0.372
10
0.150
10
2
50
734.027
7
0.504
9
3.754
10
1.577
10
2.538
10
1.577
10
2
100
0.185
6
0.888
9
0.888
9
0.888
9
21.408
10
3.037
10
2
200
-
0
9.195
10
9.195
10
9.195
10
146.047
10
9.195
10
3
25
0.224
10
0.152
10
0.152
10
0.152
10
0.373
10
0.152
10
3
50
1310.469
7
0.504
9
3.754
10
1.577
10
2.538
10
1.577
10
3
100
0.241
6
0.887
10
0.887
10
0.887
10
10.042
10
0.887
10
3
200
-
0
2.923
10
2.923
10
2.923
10
64.417
10
2.923
10
4
25
0.144
10
0.063
10
0.063
10
0.063
10
12.230
10
0.063
10
4
50
0.258
10
429.500
9
0.310
10
167.797
10
114.028
10
36.725
10
4
100
546.582
5
0.492
6
231.474
9
865.940
8
3197.110
10
1705.281
10
4
200
-
0
-
0
3614.175
4
178.004
8
7033.483
3
88.048
7
5
25
0.142
10
0.053
10
0.053
10
0.053
10
7.103
10
0.053
10
5
50
0.222
10
0.064
10
0.064
10
0.064
10
64.993
10
0.064
10
5
100
0.209
10
0.159
10
0.159
10
0.159
10
1343.978
10
0.159
10
5
200
-
0
0.750
6
57.453
7
69.771
8
40212.059
8
7975.229
9
6
25
20.364
10
5.595
10
39.244
10
28.819
10
1.745
10
5.888
10
6
50
458.286
2
1502.921
4
978.800
5
1883.995
3
14.465
10
62.004
10
6
100
-
0
-
0
-
0
-
0
308.133
10
246.377
10
6
200
-
0
-
0
-
0
-
0
6565.469
8
6739.017
8
7
25
29.031
10
2.555
10
0.883
10
13.608
10
2.272
10
5.331
10
7
50
0.164
5
395.565
8
0.665
7
0.574
7
16.690
10
20.003
10
7
100
0.178
2
5.823
3
577.320
6
5.975
4
320.205
10
239.354
10
7
200
-
0
327.499
1
2773.021
4
188.816
2
4136.122
10
3844.824
10
8
25
1306.526
2
0.112
10
0.112
10
0.112
10
2.272
10
0.112
10
8
50
-
0
0.255
10
0.255
10
0.255
10
2.728
10
0.255
10
8
100
-
0
0.892
10
0.892
10
0.892
10
18.625
10
0.892
10
8
200
-
0
3.897
10
3.897
10
3.897
10
206.273
10
3.897
10
9
25
0.233
10
869.993
10
0.705
10
0.793
10
7.477
10
0.793
10
9
50
732.793
10
-
0
869.194
6
126.817
9
224.210
10
108.803
10
9
100
-
0
-
0
-
0
-
0
5567.198
10
5759.619
10
9
200
-
0
-
0
-
0
-
0
-
0
-
0
10
24
0.264
10
90.277
10
6.327
10
0.253
10
2.045
10
0.253
10
10
51
-
0
-
0
1115.717
1
176.623
10
16.020
10
46.587
10
10
99
-
0
-
0
-
0
-
0
290.432
10
438.932
10
10
201
-
0
-
0
-
0
-
0
-
0
-
0