Improving the filtering of Branch-And-Bound MDD solver (extended)
  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.
