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 we 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 r₁, r₂, …, r_n, with the ith type having length l_i, width w_i, value v_i, and demand constraint b_i. It is required to produce, from the stock rectangle S, a_i copies of r_i, 1 ≤ i ≤ n, to maximize a₁v₁ + a₂v₂ + · + a_nv_n subject to the constraints a_i ≤ b_i. 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.