@inproceedings{0b92988010654062baead6f04fff566a,
title = "Experimental and Theoretical Analysis of Local Search Optimising OBDD Variable Orderings",
abstract = "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.",
keywords = "local search, OBDD variable ordering, run time analysis",
author = "Thomas Jansen and Christine Zarges",
note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.; 24th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2024, held as part of EvoStar 2024 ; Conference date: 03-04-2024 Through 05-04-2024",
year = "2024",
month = apr,
day = "18",
doi = "10.1007/978-3-031-57712-3_12",
language = "English",
isbn = "9783031577116",
volume = "14632",
series = "Lecture Notes in Computer Science",
publisher = "Springer Nature",
pages = "177--192",
editor = "Thomas St{\"u}tzle and Markus Wagner",
booktitle = "Evolutionary Computation in Combinatorial Optimization",
address = "Switzerland",
}