An exact two-dimensional non-guillotine cutting tree search procedure, Operations Research, vol.33, no.1, 1985, pp49-64
We consider the two-dimensional cutting problem of cutting a number of rectangular pieces from a single large rectangle so as to maximize the value of the pieces cut. We develop a lagrangean relaxation of a zero-one integer programming formulation of the problem and use it as a bound in a tree search procedure. Subgradient optimisation is used to optimize the bound derived from the lagrangean relaxation. Problem reduction tests derived from both the original problem and the lagrangean relaxation are given. Incorporating the bound and the reduction tests into a tree search procedure enables moderately sized problems to be solved.