# Improving the filtering of Branch-And-Bound MDD solver (extended)

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 34 references that are in the map.
- First posted on arXiv 24 Apr 2021.

## Builds on (most cited first, 1 of 1)

- [Improved Job sequencing Bounds from Decision Diagrams](https://mlsanity.com/paper/1908.07076/) (2019)

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

- [Domain-Independent Dynamic Programming](https://mlsanity.com/paper/2401.13883/) (2024)
- [Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection](https://mlsanity.com/paper/2211.13118/) (2022)

## Abstract (arXiv)

This paper presents and evaluates two pruning techniques to reinforce the efficiency of constraint optimization solvers based on multi-valued decision-diagrams (MDD). It adopts the branch-and-bound framework proposed by Bergman et al. in 2016 to solve dynamic programs to optimality. In particular, our paper presents and evaluates the effectiveness of the local-bound (LocB) and rough upper-bound pruning (RUB). LocB is a new and effective rule that leverages the approximate MDD structure to avoid the exploration of non-interesting nodes. RUB is a rule to reduce the search space during the development of bounded-width-MDDs. The experimental study we conducted on the Maximum Independent Set Problem (MISP), Maximum Cut Problem (MCP), Maximum 2 Satisfiability (MAX2SAT) and the Traveling Salesman Problem with Time Windows (TSPTW) shows evidence indicating that rough-upper-bound and local-bound pruning have a high impact on optimization solvers based on branch-and-bound with MDDs. In particular, it shows that RUB delivers excellent results but requires some effort when defining the model. Also, it shows that LocB provides a significant improvement automatically; without necessitating any user-supplied information. Finally, it also shows that rough-upper-bound and local-bound pruning are not mutually exclusive, and their combined benefit supersedes the individual benefit of using each technique.