Eleni Hadjiconstantinou and Nicos Christofides. An exact algorithm for general, orthogonal, two-dimensional knapsack problems. European Journal of Operational Research, 83:39-56, 1995
In this paper Hadjiconstantinou and Christofides give 7 new instances of the two-dimensional non-guillotine cutting problem. Only two of them are described in the paper. We have been able to obtain two more directly from the authors. For their experimental results they also use a subset of the instances defined by Beasley.
The algorithm, a branch-and-bound procedure using bounds obtained by lagrangean relaxation that was based on a new integer programming formulation, was implemented in FORTRAN and run on CYBER-855 using the FTN5 compiler.
| Problem | Container Size | Box Types | # Boxes | Value | Time |
| HADCHR3 | ( 30, 30) |
7 |
7 |
1178 |
532 s |
HADCHR8 | ( 40, 40) |
10 |
10 |
2517 |
800 s |
HADCHR11 | ( 30, 30) |
15 |
15 |
1270 |
800 s |
HADCHR12 | ( 40, 40) |
15 |
15 |
2949 |
65.2 |
| NGCUT4 | ( 15, 10) |
5 |
7 |
268 |
0.04 s |
| NGCUT6 | ( 15, 10) |
10 |
15 |
289 |
45.2 s |
| NGCUT7 | ( 20, 20) |
5 |
8 |
430 |
0.04 s |
| NGCUT9 | ( 20, 20) |
10 |
18 |
924 |
5.2 s |
| NGCUT12 | ( 30,30) |
10 |
22 |
1851 |
800 s |