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

K. V. Viswanathan, A. Bagchi

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 li:, width wi, value vi and demand constraint bi. S must be cut using only orthogonal guillotine cuts to produce ai copies of ri, l <_ i <_ n, so as to maiximize a1v1 + 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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.