A heuristic dynamic-programming algorithm for 2D unconstrained guillotine cutting

In this paper, a heuristic dynamic-programming recursion is proposed for solving unconstrained 2D knapsack problem efficiently. The algorithm we propose is an incompletely enumerative method, in which some intricate cutting patterns may not be enumerated. Compared with the traditional dynamic-programming, the algorithm gives a high percentage of optimal solutions (93%) with a much lowered computational complexity. Some theoretical analyses for the algorithm are performed. Computational results are given for small and medium-sized problems