The DH/KD algorithm: A hybrid approach for unconstrained two-dimensional cutting problems

We study both weighted and unweighted unconstrained two-dimensional guillotine cutting problems. We develop a hybrid approach which combines two heuristics from the literature. The first one (DH) uses a tree-search procedure introducing two strategies: Depth-first search and Hill-climbing. The second one (KD) is based on a series of one-dimensional Knapsack problems using Dynamic programming techniques. The DH/KD algorithm starts with a good initial lower bound obtained by using the KD algorithm. At each level of the tree-search, the proposed algorithm uses also the KD algorithm for constructing new lower bounds and uses another one-dimensional knapsack for constructing refinement upper bounds. The resulting algorithm can be seen as a generalization of the two heuristics and solves large problem instances very well within small computational time. Our algorithm is compared to Morabito et al.'s algorithm (the unweighted case), and to Beasley's approach (the weighted case) on some examples taken from the literature as well as randomly generated instances.