Clustering for Relaxed and Restricted Decision Diagram Bounds: When It Works and Why

Burlats, Alice;Kameugne, Roger;Pelsser, Cristel;Schaus, Pierre
(2026) The 23rd International Conference on the Integration of Constraint Programming, Artificial Intelligence and Operations Research — Location: Rabat, Morocco (26.May.2026)

Files

Clusering_for_MDD (1).pdf
  • Open Access
  • Adobe PDF
  • 661.81 KB
Download

Details

Authors
  • Burlats, Aliceorcid-logo
    Author
  • Kameugne, Rogerorcid-logo
    Author
  • Pelsser, Cristelorcid-logo
    Author
  • Schaus, Pierreorcid-logo
    Author
Abstract
Decision-Diagram-based Branch-and-Bound solves discrete optimization problems by exploiting bounds provided by two types of bounded-width decision diagram. The first is the restricted decision diagram obtained by discarding less promising states that provide primal bounds. The second is the relaxed decision diagram obtained by state merging that yields a dual bound. Their performance depends heavily on the heuristic used to discard or merge nodes. While traditional methods discard or merge nodes based on the cost, recent research suggests that clustering nodes based on state similarity (e.g., via k-means) can help produce tighter bounds. However, current clustering methods are difficult to apply to complex, non-vector states. We propose to use a more general clustering framework that accepts user-defined distance metrics, allowing it to be applied to any state definition and scales to very large state spaces. We test this approach against standard cost-based strategies on three distinct problems exhibiting different merge-function properties. We additionally introduce a definition framework that characterizes these properties. Our results show that, counter-intuitively, sophisticated clustering does not always pay off, especially when the merge operator produces states that differ greatly from the originals. We provide a detailed analysis explaining when clustering is beneficial versus when simple cost-based strategies suffice, offering some guidelines for solver configuration.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Burlats, A., Kameugne, R., Pelsser, C., & Schaus, P. (2026). Clustering for Relaxed and Restricted Decision Diagram Bounds: When It Works and Why. International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 101-118. https://doi.org/10.1007/978-3-032-27242-3_7 (Original work published 2026)