Unconstrained two-dimensional guillotine cutting

We designed and implemented a dynamic programming procedure to solve the unconstrained two-dimensional guillotine cutting problem. This procedure differs from others that have already appeared in the literature. We solved the test problems corresponding to files gcut1, ..., gcut13, available at OR-Library (these instances also can be obtained here). We solved also the test problems we called gcut1r, ..., gcut13r. These instances correspond to the test problems gcut1,..., gcut13, except that the orientation of the pieces is not fixed (that is, each piece can be rotated by ninety degree).

These tests problems were solved on a computer with two processors AMD Athlon MP 1800+, clock of 1.5 Ghz, memory of 3.5 GB and operating system Linux (distribution Debian GNU/Linux 3.0). The results obtained are shown in the tables below. The column Waste gives, for each solution found, the percentage of the area of the large rectangle that does not correspond to any item. Each instance was solved 100 times; the column Time shows the average CPU time in seconds, considering all these 100 resolutions.

Test
problem Optimal
value Waste Time
(sec) Optimal solution
Color B&W
gcut1 56460 9.664% 0.003
gcut2 60536 3.142% 0.010
gcut3 61036 2.342% 0.012
gcut4 61698 1.283% 0.022
gcut5 246000 1.600% 0.004
gcut6 238998 4.401% 0.008
gcut7 242567 2.973% 0.017
gcut8 246633 1.347% 0.062
gcut9 971100 2.890% 0.006
gcut10 982025 1.798% 0.009
gcut11 980096 1.990% 0.066
gcut12 979986 2.001% 0.140
gcut13 8997780 0.025% 144.915

Test
problem Optimal
value Waste Time
(sec) Optimal solution
Color B&W
gcut1r 58136 6.982% 0.008
gcut2r 60611 3.022% 0.021
gcut3r 61626 1.398% 0.026
gcut4r 62265 0.376% 0.042
gcut5r 246000 1.600% 0.019
gcut6r 240951 3.620% 0.032
gcut7r 245866 1.654% 0.053
gcut8r 247787 0.885% 0.135
gcut9r 971100 2.890% 0.023
gcut10r 982025 1.798% 0.071
gcut11r 980096 1.990% 0.270
gcut12r 988694 1.131% 0.325
gcut13r 9000000 0.000% 280.247

Glauber Cintra (glauber@ime.usp.br)
Ph.D. in computer science (DCC / IME / USP)