DROPS

Document

DOI: 10.4230/LIPIcs.CP.2024.28

CP for Bin Packing with Multi-Core and GPUs

Authors: Fabio Tardivo, Laurent Michel, and Enrico Pontelli

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract

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.

Cite as

Fabio Tardivo, Laurent Michel, and Enrico Pontelli. CP for Bin Packing with Multi-Core and GPUs. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 28:1-28:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{tardivo_et_al:LIPIcs.CP.2024.28,
  author =	{Tardivo, Fabio and Michel, Laurent and Pontelli, Enrico},
  title =	{{CP for Bin Packing with Multi-Core and GPUs}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{28:1--28:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.28},
  URN =		{urn:nbn:de:0030-drops-207138},
  doi =		{10.4230/LIPIcs.CP.2024.28},
  annote =	{Keywords: Constraint Propagation, Bin Packing, Parallelism, GPU, Lower Bounds}
}

Search Results

Documents authored by Tardivo, Fabio

CP for Bin Packing with Multi-Core and GPUs

Abstract

Cite as

Thanks for your feedback!

Could not send message