New upper bounds for the two-dimensional orthogonal non-guillotine cutting stock problem

The two-dimensional orthogonal non-guillotine cutting stock problem (NGCP) appears in many industries (e.g. the wood and steel industries) and consists of cutting a rectangular master surface into a number of rectangular pieces, each with a given size and value. The pieces must be cut with their edges always parallel to the edges of the master surface (orthogonal cuts). The objective is to maximize the total value of the pieces cut. New upper bounds on the optimal solution to the NGCP are described. The new bounding procedures are obtained by different relaxations of a new mathematical formulation of the NGCP. Various procedures for strengthening the resulting upper bounds and reducing the size of the original problem are discussed. The proposed new upper bounds have been experimentally evaluated on test problems derived from the literature. Comparisons with previous bounding procedures from the literature are given. The computational results indicate that these bounds are significantly better than the bounds proposed in the literature.