Abstract
This paper presents a novel best-first search algorithm, BF_CRGKP, designed to solve the Constrained Rectangular Guillotine Knapsack Problem (CRGKP) with exact optimality. By employing a monotone heuristic derived from pre-calculated dynamic programming tables, the algorithm significantly reduces the search space compared to traditional depth-first branch-and-bound methods, achieving substantial improvements in computational efficiency.
Introduction
The Constrained Rectangular Guillotine Knapsack Problem (CRGKP) is a critical optimization challenge in industrial manufacturing, such as glass, wood, and steel cutting. The objective is to maximize the total value of rectangular pieces cut from a larger stock sheet, subject to demand constraints for each piece type and a specific physical constraint: the guillotine cut.
A guillotine cut is defined as a cut that proceeds entirely from one edge of a rectangle to the opposite edge. This constraint simplifies the manufacturing process but complicates the optimization search space. Figure 1 illustrates a typical guillotine cutting pattern where pieces are arranged in a manner consistent with edge-to-edge slicing.
Methodology: The BF_CRGKP Algorithm
The proposed algorithm, BF_CRGKP, utilizes a best-first search strategy based on the $A^*$ framework. Unlike depth-first approaches that explore a single path to its conclusion, BF_CRGKP maintains a set of partial solutions and prioritizes the expansion of the most promising nodes.
Evaluation Function and Heuristic
The search is guided by an evaluation function $f(R) = g(R) + h(R)$, where $g(R)$ represents the cumulative value of pieces already placed within a rectangle $R$, and $h(R)$ is a heuristic estimate of the potential value obtainable from the remaining area. To ensure optimality, $h(R)$ must be an upper bound (admissible). The authors derive this bound by solving an unconstrained version of the problem using Gilmore and Gomory's dynamic programming recursion. To maintain high performance, these heuristic values are pre-calculated and stored in a lookup table.
Node Expansion
New nodes in the search tree are generated by combining existing rectangles from a "closed list" (CLIST). These combinations occur either horizontally or vertically, provided the resulting rectangle fits within the master stock dimensions and respects demand limits. Figure 3a demonstrates the horizontal build process, a fundamental step in generating new cutting patterns during the search.
Key Results and Insights
The BF_CRGKP algorithm demonstrates significant advantages over previous methods, particularly the depth-first branch-and-bound approach by Christofides and Whitlock.
- Search Efficiency: In benchmark tests, the best-first approach reduced the number of explored nodes from 49,638 to just 498 while reaching the same optimal solution.
- Computational Speed: In randomized trials, BF_CRGKP outperformed existing heuristics. For instance, it found an optimal solution in 1.54 seconds, whereas a comparable heuristic method required 26.65 seconds.
- Monotonicity: The authors proved the heuristic is monotone, ensuring that the first goal state reached is guaranteed to be optimal, eliminating the need for further search once a solution is found.
Conclusion
The BF_CRGKP algorithm provides an exact solution to the constrained guillotine knapsack problem with high efficiency. While best-first search requires more memory than depth-first alternatives to store the "OPEN" list of nodes, the dramatic reduction in node expansion makes it a superior choice for problems where pattern generation is computationally expensive. Future research may explore extending this method to include piece rotation and developing general criteria for selecting between best-first and depth-first search in combinatorial optimization.
Summary updated