Best-First Search Methods for Constrained Two-Dimensional Cutting Stock Problems

TLDR

Best‑first search is a widely used problem‑solving technique in artificial intelligence and operations research. The study applies best‑first search to constrained two‑dimensional cutting‑stock problems involving a stock rectangle and multiple demanded rectangle types. The authors formulate the problem as maximizing total value of produced rectangles under demand constraints, using only orthogonal guillotine cuts, and employ a best‑first tree search algorithm based on Wang’s bottom‑up approach. The algorithm guarantees optimal solutions and outperforms existing methods in efficiency.

Abstract

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 1 , r 2 , …, 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 1 v 1 + a 2 v 2 + · + a n v 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.