DROPS

Document

DOI: 10.4230/LIPIcs.CP.2026.53

GPU-Accelerated Relaxed Decision Diagrams for Branch-and-Bound Optimization

Authors: Fabio Tardivo, Laurent Michel, and Willem-Jan van Hoeve

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract

Branch-and-bound methods for combinatorial optimization rely critically on the efficient computation of strong bounds during search. Decision diagram–based optimization provides such bounds via restricted and relaxed multi-valued decision diagrams (MDDs), but compiling relaxed diagrams can become a computational bottleneck for existing solvers. We present a GPU-accelerated implementation of decision diagram–based branch-and-bound using a decoupled architecture. It separates the compilation of relaxed and restricted diagrams and coordinates them through two queues of search states. This design enables heterogeneous parallelization: restricted diagrams are compiled concurrently on CPU threads while relaxed diagrams are constructed in parallel on a GPU. The GPU implementation exploits the layered structure of decision diagrams by expanding states in parallel and performing successor generation, dominance filtering, and state merging on the GPU. Computational experiments on knapsack, maximum independent set, and Golomb ruler benchmarks demonstrate substantial performance improvements over CPU-based decision diagram solvers, including speedups of up to an order of magnitude on hard instances and the ability to solve Golomb ruler instances up to size 16.

Cite as

Fabio Tardivo, Laurent Michel, and Willem-Jan van Hoeve. GPU-Accelerated Relaxed Decision Diagrams for Branch-and-Bound Optimization. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{tardivo_et_al:LIPIcs.CP.2026.53,
  author =	{Tardivo, Fabio and Michel, Laurent and van Hoeve, Willem-Jan},
  title =	{{GPU-Accelerated Relaxed Decision Diagrams for Branch-and-Bound Optimization}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{53:1--53:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.53},
  URN =		{urn:nbn:de:0030-drops-266869},
  doi =		{10.4230/LIPIcs.CP.2026.53},
  annote =	{Keywords: Decision Diagrams, GPU Computing, Dynamic Programming, Combinatorial Optimization}
}

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

GPU-Accelerated Relaxed Decision Diagrams for Branch-and-Bound Optimization

Abstract

Cite as

CP for Bin Packing with Multi-Core and GPUs

Abstract

Cite as

Thanks for your feedback!

Could not send message