The constrained geometric knapsack problem and its shape annealing solution

Abstract: "This paper introduces a technique called shape annealing as a solution to an extension of the knapsack problem which we refer to as the constrained geometric knapsack problem. The constrained geometric knapsack problem includes geometric constraints and reduces in zero dimensions to the ordinary knapsack problem. Shape annealing, a variation of the simulated annealing stochastic optimization technique, is introduced to produce packing solutions. Shape annealing incorporates shape grammars to dictate permissible item orientations. Stochastic mutation based on a potential function creates a packing which converges toward the optimum. Results are generally sub-optimal although acceptable and the algorithm runs in polynomial time and space complexity."