Advances in discrete optimization with decision diagrams : dominance, caching and aggregation-based heuristics

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 thesis presents new ingredients to speed up this search algorithm. First, it describes how dominance rules can be utilized during the compilation of decision diagrams to detect and filter dominated nodes. The second contribution is a caching mechanism that fully exploits the structure of dynamic programming models and the way their state space is explored by the branch-and-bound algorithm. Its key idea is to prevent the repeated expansion of nodes corresponding to the same dynamic programming state 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. Finally, a procedure for deriving dual bounds and node selection heuristics through aggregate dynamic programming is detailed. Assuming a maximization problem, relaxed decision diagrams provide upper bounds through state merging while restricted decision diagrams obtain lower bounds by excluding states to limit their size. As the selection of states to merge or delete is done locally, it is very myopic to the global problem structure. This can be better captured by the proposed bounds and heuristics because they are acquired by pre-solving a so-called aggregate version of the problem. Extensive computational experiments show that the pruning brought by these additional filtering techniques and heuristics allows reducing the number of nodes expanded by the algorithm significantly and finding quality solutions earlier in the search. This results in more benchmark instances of difficult optimization problems being solved in less time, and in tighter optimality gaps when instances cannot be solved under the given time limit.