An improvement of the knapsack function based algorithm of Gilmore and Gomory for the unconstrained two-dimensional guillotine cutting problem

In this paper we tackle the unconstrained non-staged guillotine two-dimensional cutting problem (U2DCP) with rectangular pieces and one rectangular stock sheet. This problem has been widely treated in literature by exact and heuristic solution methods which use the knapsack function introduced by Gilmore and Gomory (1966) and implement more effective variants of their dynamic programming procedure to compute the related recursive expression. We highlight three errors present in the original procedure by Gilmore and Gomory (1966). The first error was noted by Herz (1972) but no correction was provided. The other two errors have never been noted before. These errors affect the accuracy of the solution and cause the increase of the computational requirements. Corrections for these errors are presented and an improved computational procedure is proposed. The new procedure has been tested on a wide set of instances (PackLib2) and compared with the best exact and heuristic methods present in literature. The experimentation shows that the procedure significantly outperforms the best dynamic programming algorithm proposed for the U2DCP and it compares well with the best heuristic and the best exact algorithm for the problem. (C) 2013 Elsevier B.V. All rights reserved.