2026-07-26T10:59:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20713 2024-08-29T08:52:52Z ddc:004 open_access

CP for Bin Packing with Multi-Core and GPUs Tardivo, Fabio Michel, Laurent Pontelli, Enrico Constraint Propagation Bin Packing Parallelism GPU Lower Bounds The BinPacking constraint models the requirements of many logistics, resource allocation, and production scheduling applications. This paper explores new avenues based on the impressive computational power of modern GPUs to propagate the BinPacking constraint. This work showcases how the perspective of massive parallelization can lead to novel approaches, such as the use of a portfolio of lower bounds, to enhance the pruning of the BinPacking constraints. It delivers insights into the design choices and challenges presented by GPU platform for constraint propagation. The paper evaluates a GPU-accelerated propagator against both sequential and parallel CPU versions, as well as state-of-the-art approaches. Comparisons across various benchmarks from the literature show strong performances with respect to both CPU versions and the standard pruning approach. When compared to techniques based on Linear Programming, our approach proves valuable for large instances or when spending extensive time to obtain the best possible bound is not convenient. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fabio Tardivo and Laurent Michel and Enrico Pontelli 2024 Is Part Of LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2024.28 urn:nbn:de:0030-drops-207138 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.28 eng https://creativecommons.org/licenses/by/4.0/legalcode