Alberto Caprara and Michele Monaci. On the two-dimensional Knapsack Problem. Operations Research Letters, 32:5-14, 2004
-
CGCUT1-CGCUT3
GCUT1-GCUT13
OKP1-OKP5
WANG20
In this article Caprara and Monaci solve many two-dimensional knapsack problems from the literature. For that purpose they devised four different branch-and-bound algorithms A0, A1, A3, and A4 that differ in the search procedure.
The algorithms were implemented in ANSI C. The computational results have been obtained on an Intel Pentium III clocked at 800MHz. For each run there was a time limit of 1800s after which the algorithm was aborted.
Caprara and Monaci solved a slight modification of the GCUT instances. As defined by Beasley the number of boxes per box type is unbounded. In this paper the at most one box per type is used.
| Problem | Container Size | Box Types | # Boxes | Value | Time(A0) | Time(A1) | Time(A2) | Time(A3) |
| CGCUT1 | ( 15, 10) |
7 |
16 |
244 |
0.3 s |
1.47 s |
1.46 s |
1.46 s |
| CGCUT2 | ( 40, 70) |
10 |
23 |
2892 |
>1800 s |
>1800 s |
533.45 s |
531.93 s |
| CGCUT3 | ( 40, 70) |
20 |
62 |
1860 |
23.76 s |
5.06 s |
4.59 s |
4.58 s |
| GCUT1 | ( 250, 250) |
10 |
10 |
48368 |
0.00 s |
0.00 s |
0.01 s |
0.01 s |
| GCUT2 | ( 250, 250) |
20 |
20 |
59798 |
0.52 s |
0.19 s |
25.75 s |
0.22 s |
| GCUT3 | ( 250, 250) |
30 |
30 |
61275 |
2.80 s |
2.16 s |
276.37 s |
3.24 s |
| GCUT4 | ( 250, 250) |
50 |
50 |
61380 |
>1800 |
346.99 s |
>1800 |
376.52 s |
| GCUT5 | ( 500, 500) |
10 |
10 |
195582 |
0.00 s |
0.50 s |
0.03 s |
0.50 s |
| GCUT6 | ( 500, 500) |
20 |
20 |
236305 |
0.06 s |
0.09 s |
9.71 s |
0.12 s |
| GCUT7 | ( 500, 500) |
30 |
30 |
240143 |
1.31 s |
0.63 s |
354.50 s |
1.07 s |
| GCUT8 | ( 500, 500) |
50 |
50 |
245758 |
1202.09 s |
136.71 s |
>1800 s |
168.50 s |
| GCUT9 | ( 1000, 1000) |
10 |
10 |
939600 |
0.01 s |
0.09 s |
0.05 s |
0.08 s |
| GCUT10 | ( 1000, 1000) |
20 |
20 |
937349 |
0.01 s |
0.13 s |
6.49 s |
0.14 s |
| GCUT11 | ( 1000, 1000) |
30 |
30 |
969709 |
16.72 s |
14.76 s |
>1800 s |
16.30 s |
| GCUT12 | ( 1000, 1000) |
50 |
50 |
979521 |
63.45 s |
16.85 s |
>1800 s |
25.39 s |
| GCUT13 | ( 3000, 3000) |
32 |
32 |
<8408316 |
>1800 s |
>1800 s |
>1800 s |
>1800 s |
| OKP1 | ( 100, 100) |
15 |
52 |
27718 |
24.06 s |
25.46 s |
72.20 s |
35.84 s |
| OKP2 | ( 100, 100) |
30 |
30 |
22502 |
>1800 s |
>1800 s |
1535.95 s |
1559.00 s |
| OKP3 | ( 100, 100) |
30 |
30 |
24019 |
21.36 s |
1.91 s |
465.57 s |
10.63 s |
| OKP4 | ( 100, 100) |
33 |
61 |
32893 |
40.40 s |
2.13 s |
0.85 s |
4.05 s |
| OKP5 | ( 100, 100) |
29 |
97 |
27923 |
>1800 s |
>1800 s |
513.06 s |
488.27 s |
| WANG20 | ( 70, 40) |
20 |
42 |
2726 |
6.75 s |
6.31 s |
17.84 s |
2.72 s |