Search Results

Documents authored by Van Hoeve, Willem-Jan

Document
Invited Talk
DOI: 10.4230/LIPIcs.CP.2026.1
Decision Diagrams for Constraint Reasoning and Optimization (Invited Talk)

Authors: Willem-Jan van Hoeve

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

Abstract
Since their original inception to represent Boolean functions for verification problems in the 1950s, decision diagrams have found wide applicability across academic disciplines and industry. This presentation discusses the use of decision diagrams as a compact representation of feasible solutions to constrained optimization problems, where solutions correspond to paths in a layered graph. By using relaxed and restricted decision diagrams of bounded size, one can balance the strength of the representation and computational effort. We highlight three roles of decision diagrams in constrained optimization. First, they enable a model-and-solve approach for dynamic programming, where a dynamic programming model and a merging rule define the compilation of decision diagrams that yield primal and dual bounds within a state-based search. Second, in constraint programming, they strengthen constraint propagation through multi-valued decision diagrams and provide optimization bounds within the search process. Third, in integer programming, they yield arc-flow formulations and establish connections with Dantzig–Wolfe decomposition, leading to strong bounds and state-of-the-art computational results. These approaches are illustrated on applications including machine scheduling, graph multi-coloring, and vehicle routing, where decision diagram-based methods have led to substantial improvements on benchmark instances. They have also been adopted in practice, both as a dual bounding component within a general-purpose optimization solver and in industrial applications for routing and scheduling.
Cite as

Willem-Jan van Hoeve. Decision Diagrams for Constraint Reasoning and Optimization (Invited Talk). In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{vanhoeve:LIPIcs.CP.2026.1,
  author =	{van Hoeve, Willem-Jan},
  title =	{{Decision Diagrams for Constraint Reasoning and Optimization}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{1:1--1:1},
  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.1},
  URN =		{urn:nbn:de:0030-drops-266350},
  doi =		{10.4230/LIPIcs.CP.2026.1},
  annote =	{Keywords: Decision diagrams, constraint programming, dynamic programming, integer programming, arc-flow formulations}
}
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.2022.24
Heuristics for MDD Propagation in HADDOCK

Authors: Rebecca Gentzel, Laurent Michel, and Willem-Jan van Hoeve

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
Haddock, introduced in [R. Gentzel et al., 2020], is a declarative language and architecture for the specification and the implementation of multi-valued decision diagrams. It relies on a labeled transition system to specify and compose individual constraints into a propagator with filtering capabilities that automatically deliver the expected level of filtering. Yet, the operational potency of the filtering algorithms strongly correlate with heuristics for carrying out refinements of the diagrams. This paper considers how to empower Haddock users with the ability to unobtrusively specify various such heuristics and derive the computational benefits of exerting fine-grained control over the refinement process.
Cite as

Rebecca Gentzel, Laurent Michel, and Willem-Jan van Hoeve. Heuristics for MDD Propagation in HADDOCK. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gentzel_et_al:LIPIcs.CP.2022.24,
  author =	{Gentzel, Rebecca and Michel, Laurent and van Hoeve, Willem-Jan},
  title =	{{Heuristics for MDD Propagation in HADDOCK}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.24},
  URN =		{urn:nbn:de:0030-drops-166534},
  doi =		{10.4230/LIPIcs.CP.2022.24},
  annote =	{Keywords: Decision Diagrams}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.26
From Cliques to Colorings and Back Again

Authors: Marijn J. H. Heule, Anthony Karahalios, and Willem-Jan van Hoeve

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
We present an exact algorithm for graph coloring and maximum clique problems based on SAT technology. It relies on four sub-algorithms that alternatingly compute cliques of larger size and colorings with fewer colors. We show how these techniques can mutually help each other: larger cliques facilitate finding smaller colorings, which in turn can boost finding larger cliques. We evaluate our approach on the DIMACS graph coloring suite. For finding maximum cliques, we show that our algorithm can improve the state-of-the-art MaxSAT-based solver IncMaxCLQ, and for the graph coloring problem, we close two open instances, decrease two upper bounds, and increase one lower bound.
Cite as

Marijn J. H. Heule, Anthony Karahalios, and Willem-Jan van Hoeve. From Cliques to Colorings and Back Again. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 26:1-26:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{heule_et_al:LIPIcs.CP.2022.26,
  author =	{Heule, Marijn J. H. and Karahalios, Anthony and van Hoeve, Willem-Jan},
  title =	{{From Cliques to Colorings and Back Again}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{26:1--26:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.26},
  URN =		{urn:nbn:de:0030-drops-166558},
  doi =		{10.4230/LIPIcs.CP.2022.26},
  annote =	{Keywords: Graph coloring, maximum clique, Boolean satisfiability}
}
Document
DOI: 10.4230/DagRep.8.2.26
Planning and Operations Research (Dagstuhl Seminar 18071)

Authors: J. Christopher Beck, Daniele Magazzeni, Gabriele Röger, and Willem-Jan Van Hoeve

Published in: Dagstuhl Reports, Volume 8, Issue 2 (2018)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 18071 "Planning and Operations Research". The seminar brought together researchers in the areas of Artificial Intelligence (AI) Planning, Constraint Programming, and Operations Research. All three areas have in common that they deal with complex systems where a huge space of interacting options makes it almost impossible to humans to take optimal or even good decisions. From a historical perspective, operations research stems from the application of mathematical methods to (mostly) industrial applications while planning and constraint programming emerged as subfields of artificial intelligence where the emphasis was traditionally more on symbolic and logical search techniques for the intelligent selection and sequencing of actions to achieve a set of goals. Therefore operations research often focuses on the allocation of scarce resources such as transportation capacity, machine availability, production materials, or money, while planning focuses on the right choice of actions from a large space of possibilities. While this difference results in problems in different complexity classes, it is often possible to cast the same problem as an OR, CP, or planning problem. In this seminar, we investigated the commonalities and the overlap between the different areas to learn from each other's expertise, bring the communities closer together, and transfer knowledge about solution techniques that can be applied in all areas.
Cite as

J. Christopher Beck, Daniele Magazzeni, Gabriele Röger, and Willem-Jan Van Hoeve. Planning and Operations Research (Dagstuhl Seminar 18071). In Dagstuhl Reports, Volume 8, Issue 2, pp. 26-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{beck_et_al:DagRep.8.2.26,
  author =	{Beck, J. Christopher and Magazzeni, Daniele and R\"{o}ger, Gabriele and Van Hoeve, Willem-Jan},
  title =	{{Planning and Operations Research (Dagstuhl Seminar 18071)}},
  pages =	{26--63},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{8},
  number =	{2},
  editor =	{Beck, J. Christopher and Magazzeni, Daniele and R\"{o}ger, Gabriele and Van Hoeve, Willem-Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.2.26},
  URN =		{urn:nbn:de:0030-drops-92894},
  doi =		{10.4230/DagRep.8.2.26},
  annote =	{Keywords: Artificial Intelligence, Automated Planning and Scheduling, Constraint Programming, Dynamic Programming, Heuristic Search, Mixed Integer Programming, Operations Research, Optimization, Real-world Applications, Reasoning under Uncertainty}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact