Best-first search methods for constrained two-dimensional cutting stock problems

Best-first search is a widely used problem solving technique in the field of artificial intelligence. The method has useful applications in operations research as well. Here the authors describe an application to constrained two-dimensional cutting stock problems of the following type: A stock rectangle S of dimensions (L,W) is supplied. There are n types of demanded rectangles r1,r2,...,rn, with the ith type having length li, width wi, value vi, and demand constraint bi. It is required to produce, from the stock rectangle S, ai copies of ri, 1•i•n, to maximize a1v1+a2v2+ëëë+anvn subject to the constraints ai•bi. Only orthogonal guillotine cuts are permitted. All parameters are integers. A best-first tree search algorithm based on Wang’s bottom-up approach is described that guarantees optimal solutions and is more efficient than existing methods.