Silvano Martello and Michele Monaci and Daniele Vigo. An exact approach to the strip-packing problem. INFORMS Journal on Computing, 15:310-319, 2003
-
HT1-HT9
CGCUT1-CGCUT3
GCUT1-GCUT4
NGCUT1-NGCUT12
BENG1-BENG10
Martello, Monaci and Vigo propose a new relaxation that produces good lower bounds and
gives information to obtain effective heuristic algorithms. These results are used in a branch-and-bound
algorithm, which was able to solve test instances involving up to 200 items.
The algorithms were coded in FORTRAN 77 and run on a Pentium III 800 MHz.
The instances CGCUT, GCUT, NGCUT and BENG were transformed into strip-packing instances by using the items
sizes and bin width.
| UBl | best value found, at the root node, by a heuristic from the literature |
| UB | best heuristic value found at the root node |
| troot | CPU time, spent at the root node |
| z | best solution value found by branch-and-bound within 3600 CPU seconds |
| %gap | percentage gap (100(z-L4)/z) |
tb&b
| CPU time, spent by branch -and-bound after the root node |
|
| Problem | Container Size | Box Types | # Boxes | UBl | UB | troot | z | %gap | tb&b |
| HT1 | (20, ) |
16 |
22 |
20 |
10.84 s |
20 |
0.00 |
0.00 s |
|
| HT2 | (20, ) |
17 |
23 |
21 |
623.53 s |
20 |
0.00 |
2419.72 s |
|
| HT3 | (20, ) |
16 |
22 |
20 |
500.75 s |
20 |
0.00 |
0.00 s |
|
| HT4 | (40, ) |
25 |
16 |
15 |
8.26 s |
15 |
0.00 |
0.00 s |
|
| HT5 | (40, ) |
25 |
16 |
15 |
20.29 s |
15 |
0.00 |
0.00 s |
|
| HT6 | (40, ) |
25 |
16 |
15 |
16.94 s |
15 |
0.00 |
0.00 s |
|
| HT7 | (60, ) |
28 |
33 |
31 |
643.96 s |
31 |
3.23 |
T.L |
|
| HT8 | (60, ) |
29 |
32 |
31 |
630.17 s |
31 |
3.23 |
T.L. |
|
| HT9 | (60, ) |
28 |
33 |
30 |
0.00 s |
30 |
0.00 |
0.00 s |
|
| CGCUT1 | ( , 10) |
7 |
16 |
25 |
23 |
11.48 s |
23 |
0.00 s |
0.00 s |
| CGCUT2 | ( , 70) |
10 |
23 |
77 |
68 |
2178.39 s |
67 |
5.97 |
T.L. |
| CGCUT3 | ( , 70) |
20 |
62 |
676 |
670 |
2996.11 s |
670 |
5.07 |
T.L. |
| GCUT1 | ( , 250) |
10 |
10 |
1016 |
1016 |
0.00 s |
1016 |
0.00 |
0.00 s |
| GCUT2 | ( , 250) |
20 |
20 |
1348 |
1348 |
3393.61 s |
1208 |
6.21 |
T.L. |
| GCUT3 | ( , 250) |
30 |
30 |
1803 |
1803 |
0.00 s |
1803 |
0.00 |
0.00 s |
| GCUT4 | ( , 250) |
50 |
50 |
3189 |
3077 |
3944.81 s |
3077 |
6.64 |
T.L. |
| NGCUT1 | ( , 10) |
5 |
10 |
23 |
23 |
0.05 s |
23 |
0.00 |
0.00 s |
| NGCUT2 | ( , 10) |
7 |
17 |
31 |
30 |
11.31 s |
30 |
0.00 |
0.00 s |
| NGCUT3 | ( , 10) |
10 |
21 |
32 |
28 |
27.01 |
28 |
0.00 |
0.00 |
| NGCUT4 | ( , 10) |
5 |
7 |
20 |
20 |
0.00 s |
20 |
0.00 |
0.00 s |
| NGCUT5 | ( , 10) |
7 |
14 |
36 |
36 |
0.00 s |
36 |
0.00 |
0.00 s |
| NGCUT6 | ( , 10) |
10 |
15 |
36 |
31 |
727.20 s |
31 |
0.00 |
0.00 s |
| NGCUT7 | ( , 20) |
5 |
8 |
20 |
20 |
0.00 s |
20 |
0.00 |
0.00 s |
| NGCUT8 | ( , 20) |
7 |
13 |
38 |
33 |
53.09 s |
33 |
0.00 |
0.00 s |
| NGCUT9 | ( , 20) |
10 |
18 |
56 |
50 |
1129.01 |
50 |
2.00 |
T.L. |
| NGCUT10 | ( , 30) |
5 |
13 |
82 |
80 |
0.18 s |
80 |
0.00 |
0.00 s |
| NGCUT11 | ( , 30) |
7 |
15 |
57 |
52 |
483.01 s |
52 |
0.00 |
0.00 s |
| NGCUT12 | ( ,30) |
10 |
22 |
87 |
87 |
0.00 s |
87 |
0.00 |
0.00 s |
| Beng1 | (25 ,) |
20 |
33 |
31 |
511.58 s |
30 |
0.00 |
399.79 s |
|
| Beng2 | (25 ,) |
40 |
59 |
58 |
627.34 s |
58 |
1.72 |
T.L. |
|
| Beng3 | (25 ,) |
60 |
86 |
85 |
620.37 s |
85 |
1.18 |
T.L. |
|
| Beng4 | (25 ,) |
80 |
109 |
108 |
1120.61 s |
108 |
0.93 |
T.L. |
|
| Beng5 | (25 ,) |
100 |
135 |
134 |
500.62 s |
134 |
0.00 |
0.00 s |
|
| Beng6 | (40 ,) |
40 |
37 |
37 |
620.28 s |
37 |
2.7 |
T.L. |
|
| Beng7 | (40 ,) |
80 |
68 |
67 |
0.56 s |
67 |
0.00 |
0.00 s |
|
| Beng8 | (40 ,) |
120 |
102 |
101 |
500.54 s |
101 |
0.00 |
0.00 s |
|
| Beng9 | (40 ,) |
160 |
126 |
126 |
0.03 s |
126 |
0.00 |
0.00 s |
|
| Beng10 | (40 ,) |
200 |
156 |
156 |
0.03 s |
156 |
0.00 |
0.00 s |
|