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

The two-dimensional orthogonal non-guillotine cutting stockproblem (NGCP) appears in many industries (e.g. the wood andsteel industries) and consists of cutting a rectangular mastersurface into a number of rectangular pieces, each with a givensize and value. The pieces must be cut with their edges alwaysparallel 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 relaxationsof a new mathematical formulation of the NGCP. Various proceduresfor strengthening the resulting upper bounds and reducing thesize of the original problem are discussed. The proposed newupper bounds have been experimentally evaluated on test problemsderived from the literature. Comparisons with previous boundingprocedures from the literature are given. The computationalresults indicate that these bounds are significantly betterthan the bounds proposed in the literature.