Exact algorithms for unconstrained three-dimensional cutting problems: a comparative study

In this paper we propose two exact algorithms for solving the three-dimensional cutting (3DC) problem. We study the two cases of the unconstrained 3DC problem: (i) only one large pallet is considered, denoted U_3DC, and (ii) the general version, U_G3DC, in which different large pallets are considered. For both cases of the problem, we consider that there is unlimited quantity of each type of pieces to cut, and that all cuts are of guillotine type. We propose a first exact algorithm for the U_3DC problem. The algorithm is an adaptation of Gilmore and Gomory's approach initially proposed for solving the unconstrained two-dimensional guillotine cutting problem. We then present a second algorithm for the same problem. This algorithm is mainly based upon a graph search procedure using a depth-first search strategy. This algorithm is a straightforward extension of the two-dimensional guillotine cutting approach proposed earlier. We later show how we can extend the dynamic programming based algorithm for exactly solving the U_G3DC problem. Finally, we undertake an extensive experimental study with a large number of problem instances extracted from the literature and compare the performances of both algorithms.