An Exact Best-First Search Procedure for the Constrained Rectangular Guillotine Knapsack Problem

Abstract

The Constrained Rectangular Guillotine Knapsack Problem (CRGKP) is a variant of the two-dimensional cutting stock problem. In the CRGKP, a stock rectangle of dimensions (L,W) is given. There are n different types of demanded rectangles, with the ith type ri having length 1i, width wi, value vi and demand constraint bi. S must be cut using only orthogonal guillotine cuts to produce ai copies of ri, 1 ≤ i ≤ n, so as to maximize alvl + a2v2 +....+ anvn, subject to the constraints ai ≤ bi, l ≤ i ≤ n. All parameters are integers. Here a new best-first search algorithm for the CRGKP is described. The heuristic estimate function is monotone, and optimal solutions are guaranteed. Computational results indicate that this method is superior in performance to the two existing algorithms for the problem.