SHAPE ANNEALING SOLUTION TO THE CONSTRAINED GEOMETRIC KNAPSACK-PROBLEM

The paper introduces a technique called shape annealing as a solution to an extension of the knapsack problem which is referred to as the co nstrained geometric knapsack problem that is used for the layout or pa cking of parts, components, and configurations. Shape annealing, a var iation of the simulated annealing stochastic optimization technique, i ncorporates shape grammars to dictate permissible item orientations in packing problems. Stochastic mutation based on a potential function c reates a packing that converges toward the optimum. Results are accept able but generally not provably optimal, and the algorithm runs in pol ynomial time and space complexity. The constrained geometric knapsack problem includes geometric constraints and reduces in zero dimensions to the ordinary knapsack problem. The problem has a wide variety of ap plications in design and manufacturing.