CONSTRAINED 2-DIMENSIONAL CUTTING - AN IMPROVEMENT OF CHRISTOFIDES AND WHITLOCK EXACT ALGORITHM

Christofides and Whitlock have developed a top-down algorithm which co mbines in a nice tree search procedure Gilmore and Gomory's algorithm and a transportation routine called at each node of the tree for solvi ng exactly the constrained two-dimensional cutting problem. Recently, another bottom-up algorithm has been developed and reported as being m ore efficient. In this paper, we propose a modification to the branchi ng strategy and we introduce the one-dimensional bounded knapsack in t he original Christofides and Whitlock algorithm, Then, by exploiting d ynamic programming properties we obtain good lower and upper bounds wh ich lead to significant branching cuts, resulting in st drastic reduct ion of calls of the transportation routine. Finally, we propose an inc remental solution of the numerous generated transportation problems. T he resulting algorithm reveals superior performance to other known alg orithms.