Experimental and Theoretical Analysis of Local Search Optimising OBDD Variable Orderings

Building on recent interest in the analysis of the performance of randomised search heuristics for permutation problems we investigate the performance of local search when applied to the classical combinatorial optimisation problem of finding an optimal variable ordering for ordered binary decision diagrams, a data structure for Boolean functions. This brings theory-oriented analysis towards a practically relevant combinatorial optimisation problem. We investigate a class of benchmark functions as well as the leading bit of binary addition, both Boolean functions where the variable ordering makes the difference between linear and exponential size (measured in the number of variables). We present experiments with two local search variants using five different operators for permutations from the literature. These experiments as well as theoretical results show which operators and local search variants perform best, improving our understanding of the operators and local search in combinatorial optimisation.