A knapsack problem for rectangles under the gravity center constraints

We have a set of rectangles with pre-defined widths, lengths, and masses and a knapsack with known width and length. Our goal is to select a subset of items and find their packing into the knapsack without overlapping to minimize the total empty space in the knapsack, while deviation of the total gravity center of such items from the geometric center of the knapsack does not exceed some threshold in both axes. We use the item permutations to represent the solutions and the skyline heuristic as a decoding procedure. The gravity center constraint is relaxed and included into the objective function with a penalty. To find the best permutation, we apply the simulated annealing algorithm with swap neighborhood and a special rule for returning into the feasible domain. Computational results for test instances with known optimal solutions are discussed. Tab. 2, illustr. 3, bibliogr. 14.