Article:

Sándor Fekete and Jörg Schepers. An Exact Algorithm for Higher-Dimensional Orthogonal Packing. 2004, Revised for Operations Research

Instances defined:

OKP1-OKP5

Instances used:

CGCUT1-CGCUT3
GCUT1-GCUT13
HADCHR
NGCUT1-NGCUT12
WANG20

Results:

Fekete and Schepers define five new two-dimensional knapsack instances. Many others are solved to optimality as well. In this paper they present a nested branch-and-bound procedure. The inner branch-and-bound algorithm enumerates so called packing classes.

The algorithm is implemented in C++ and run on a PC equipped with an Intel Pentium IV clocked at 3GHz.

Problem Container Size Box Types # Boxes Value Time
okp1
(100, 100)
15
52
27718
4.80 s
okp2
( 100, 100)
30
30
22502
13.67 s
okp3
(100, 100)
30
30
24019
5.17 s
okp4
(100, 100)
33
61
32893
7.69 s
okp5
(100, 100)
29
97
27923
2.62 s
cgcut1
(15, 10)
7
16
244
< 0.01 s
cgcut2
(40, 70)
10
23
<= 2892
> 1800.00 s
cgcut3
(40, 70)
20
62
1860
0.22 s
GCUT1
( 250, 250)
10
10
48368
0.02 s
GCUT2
( 250, 250)
20
20
59768
0.46 s
GCUT3
( 250, 250)
30
30
61275
4.59 s
GCUT4
( 250, 250)
50
50
61380
199.84 s
GCUT5
( 500, 500)
10
10
195582
0.03 s
GCUT6
( 500, 500)
20
20
236305
0.25 s
GCUT7
( 500, 500)
30
30
238974
1.34 s
GCUT8
( 500, 500)
50
50
245758
72.91 s
GCUT9
( 1000, 1000)
10
10
923708
0.02 s
GCUT10
( 1000, 1000)
20
20
932696
0.06 s
GCUT11
( 1000, 1000)
30
30
959915
2.75 s
GCUT12
( 1000, 1000)
50
50
976877
0.27 s
GCUT13
( 3000, 3000)
32
32
no solution
>1800
hadchr3
(30, 30)
7
7
1178
< 0.01 s
hadchr8
(40, 40)
10
10
2517
< 0.01 s
hadchr11
(30, 30)
15
15
1270
0.01 s
hadchr12
(40, 40)
15
15
2949
0.02 s
ngcut1
(10, 10)
5
10
0.01 s
ngcut2
(10, 10)
7
17
< 0.01 s
ngcut3
(10, 10)
10
21
< 0.01 s
ngcut4
(15, 10)
5
7
< 0.01 s
ngcut5
(15, 10)
7
14
< 0.01 s
ngcut6
(15, 10)
10
15
0.01 s
ngcut7
(20, 20)
5
8
< 0.01 s
ngcut8
(20, 20)
7
13
0.01 s
ngcut9
(20, 20)
10
18
0.01 s
ngcut10
(30, 30)
5
13
< 0.01 s
ngcut11
(30, 30)
7
15
0.01 s
ngcut12
(30, 30)
10
22
0.01 s
wang20
(70, 40)
20
42
2726
0.95 s