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

@inproceedings{Burlats2026,
	title        = {Clustering for Relaxed and Restricted Decision Diagram Bounds: When It Works and Why},
	author       = {Alice Burlats and Roger Kameugne and Cristel Pelsser and Pierre Schaus},
	year         = 2026,
	month        = may,
	booktitle    = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research ({CPAIOR} 2026)},
	publisher    = {Springer Nature Switzerland},
	address      = {Cham},
	series       = {Lecture Notes in Computer Science},
	pages        = {101--118},
	isbn         = {978-3-032-27241-6},
	doi          = {10.1007/978-3-032-27242-3_7},
	url          = {https://pschaus.github.io/assets/publi/cpaior26-clustering.pdf},
	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.},
	groups       = {International Conferences},
	keywords     = {Decision Diagrams, Clustering, Branch-and-Bound, Generalized Hyperplan Partitioning, Discrete Optimization}
}