2026-07-28T21:27:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20029 2024-06-06T06:21:17Z ddc:004 open_access

Shadoks Approach to Knapsack Polygonal Packing (CG Challenge) da Fonseca, Guilherme D. Gerard, Yan Packing polygons heuristics integer programming computational geometry We describe the heuristics used by the Shadoks team in the CG:SHOP 2024 Challenge. Each instance consists of a convex polygon called container and a multiset of items, where each item is a simple polygon and has an associated value. The goal is to pack some of the items inside the container using translations, in order to maximize the sum of their values. Our strategy consists of obtaining good initial solutions and improving them with local search. To obtain the initial solutions we used integer programming and a carefully designed greedy approach. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guilherme D. da Fonseca and Yan Gerard 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.84 urn:nbn:de:0030-drops-200293 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.84 eng https://creativecommons.org/licenses/by/4.0/legalcode