A RECURSIVE EXACT ALGORITHM FOR WEIGHTED 2-DIMENSIONAL CUTTING

Gilmore and Gomory's algorithm is one of the better actually known exa ct algorithms for solving unconstrained guillotine two-dimensional cut ting problems. Herz's algorithm is more effective, but only for the un weighted case. We propose a new exact algorithm adequate for both weig hted and unweighted cases, which is more powerful than both algorithms . The algorithm uses dynamic programming procedures and one-dimensiona l knapsack problem to obtain efficient lower and upper bounds and impo rtant optimality criteria which permit a significant branching cut in a recursive tree-search procedure. Recursivity, computational power, a dequateness to parallel implementations, and generalization for solvin g constrained two-dimensional cutting problems, are some important fea tures of the new algorithm.