Constrained two-dimensional cutting: An improvement of Christofides and Whitlock's exact algorithm

Christofides and Whitlock have developed a top-down algorithm which combines in a nice tree search procedure Gilmore and Gomory's algorithm and a transportation routine called at each node of the tree for solving exactly the constrained two-dimensional cutting problem. Recently, another bottom-up algorithm has been developed and reported as being more efficient. This paper proposes a modification to the branching strategy and introduces the one-dimensional bounded knapsack in the original Christofides and Whitlock algorithm. Then, by exploiting dynamic programming properties good lower and upper bounds are obtained, which lead to significant branching cuts, resulting in a drastic reduction of calls of the transportation routine. Finally, the paper proposes an incremental solution of the numerous generated transportation problems. The resulting algorithm reveals superior performance to other known algorithms.