  The branch-and-bound algorithm based on decision diagrams introduced by
Bergman et al. in 2016 is a framework for solving discrete optimization
problems with a dynamic programming formulation. It works by compiling a series
of bounded-width decision diagrams that can provide lower and upper bounds for
any given subproblem. Eventually, every part of the search space will be either
explored or pruned by the algorithm, thus proving optimality. This paper
presents new ingredients to speed up the search by exploiting the structure of
dynamic programming models. The key idea is to prevent the repeated expansion
of nodes corresponding to the same dynamic programming states by querying
expansion thresholds cached throughout the search. These thresholds are based
on dominance relations between partial solutions previously found and on the
pruning inequalities of the filtering techniques introduced by Gillard et al.
in 2021. Computational experiments show that the pruning brought by this
caching mechanism allows significantly reducing the number of nodes expanded by
the algorithm. This results in more benchmark instances of difficult
optimization problems being solved in less time while using narrower decision
diagrams.
