# Peel-and-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams

arXiv: https://arxiv.org/abs/2205.05216 · HTML: https://mlsanity.com/paper/2205.05216/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 May 2022.

## Built on by (most cited first, 4 of 4)

- [Constraints First: A New MDD-based Model to Generate Sentences Under Constraints](https://mlsanity.com/paper/2309.12415/) (2023)
- [Intertwining CP and NLP: The Generation of Unreasonably Constrained Sentences](https://mlsanity.com/paper/2406.15473/) (2024)
- [Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection](https://mlsanity.com/paper/2211.13118/) (2022)
- [A Clustering-Based Variable Ordering Framework for Relaxed Decision Diagrams for Maximum Weighted Independent Set Problem](https://mlsanity.com/paper/2512.15198/) (2025)

## Abstract (arXiv)

Decision diagrams are an increasingly important tool in cutting-edge solvers for discrete optimization. However, the field of decision diagrams is relatively new, and is still incorporating the library of techniques that conventional solvers have had decades to build. We drew inspiration from the warm-start technique used in conventional solvers to address one of the major challenges faced by decision diagram based methods. Decision diagrams become more useful the wider they are allowed to be, but also become more costly to generate, especially with large numbers of variables. We present a method of peeling off a sub-graph of previously constructed diagrams and using it as the initial diagram for subsequent iterations that we call peel-and-bound. We test the method on the sequence ordering problem, and our results indicate that our peel-and-bound scheme generates stronger bounds than a branch-and-bound scheme using the same propagators, and at significantly less computational cost.