Research output: Contribution to journal › Article › peer-review
A Knapsack Problem for Rectangles under Center-of-Gravity Constraints. / Shperling, S. M.; Kochetov, Yu A.
In: Journal of Applied and Industrial Mathematics, Vol. 16, No. 3, 05.2022, p. 563-571.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - A Knapsack Problem for Rectangles under Center-of-Gravity Constraints
AU - Shperling, S. M.
AU - Kochetov, Yu A.
N1 - Funding Information: The work was carried out within the framework of the state assignment for Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, project no. FWNF–2022–0019. Publisher Copyright: © 2022, Pleiades Publishing, Ltd.
PY - 2022/5
Y1 - 2022/5
N2 - We have a set of rectangles with predefined widths, lengths, and masses and a knapsack ofknown width and length. Our goal is to select a subset of items and find their packing into theknapsack without overlapping so as to minimize the total empty space in the knapsack. Thedeviation of the center of gravity of the items from the knapsack geometric center must not exceedsome threshold along both axes. We use item permutations to represent solutions and the skylineheuristic as a decoding procedure. The center-of-gravity constraint is relaxed and included intothe objective function with penalty. To find the best permutation, we apply the simulatedannealing algorithm with swap neighborhood and a special rule for returning into the feasibledomain. Computational results for test instances with known optimal solutions are discussed.
AB - We have a set of rectangles with predefined widths, lengths, and masses and a knapsack ofknown width and length. Our goal is to select a subset of items and find their packing into theknapsack without overlapping so as to minimize the total empty space in the knapsack. Thedeviation of the center of gravity of the items from the knapsack geometric center must not exceedsome threshold along both axes. We use item permutations to represent solutions and the skylineheuristic as a decoding procedure. The center-of-gravity constraint is relaxed and included intothe objective function with penalty. To find the best permutation, we apply the simulatedannealing algorithm with swap neighborhood and a special rule for returning into the feasibledomain. Computational results for test instances with known optimal solutions are discussed.
KW - 2D packing
KW - center-of-gravity constraint
KW - local search
KW - skyline heuristic
UR - http://www.scopus.com/inward/record.url?scp=85144227929&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/616d0a4c-743f-31c8-9167-b937c4f06ab5/
U2 - 10.1134/S199047892203019X
DO - 10.1134/S199047892203019X
M3 - Article
AN - SCOPUS:85144227929
VL - 16
SP - 563
EP - 571
JO - Journal of Applied and Industrial Mathematics
JF - Journal of Applied and Industrial Mathematics
SN - 1990-4789
IS - 3
ER -
ID: 41152787