AN EXACT ALGORITHM FOR GENERAL, ORTHOGONAL, 2-DIMENSIONAL KNAPSACK-PROBLEMS

We present a new exact tree-search procedure for solving two-dimension al knapsack problems in which a number of small rectangular pieces, ea ch of a given size and value, are required to be cut from a large rect angular stock plate. The objective is to maximise the value of pieces cut or minimise the wastage. We consider the case where there is a max imum number of times that a piece may be used in a cutting pattern. Th e algorithm limits the size of the tree search by using a bound derive d from a Lagrangean relaxation of a 0-1 integer programming formulatio n of the problem. Subgradient optimisation is used to optimise this bo und. Reduction tests derived from both the original problem and the La grangean relaxation produce substantial computational gains. The compu tational performance of the algorithm indicates that it is an effectiv e procedure capable of solving optimally practical two-dimensional cut ting problems of medium size.