Experimental and Theoretical Analysis of Local Search Optimising OBDD Variable Orderings

Thomas Jansen*, Christine Zarges

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

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.
Original languageEnglish
Title of host publicationEvolutionary Computation in Combinatorial Optimization – 24th European Conference, EvoCOP 2024
PublisherSpringer Nature
Publication statusAccepted/In press - 10 Jan 2024

Fingerprint

Dive into the research topics of 'Experimental and Theoretical Analysis of Local Search Optimising OBDD Variable Orderings'. Together they form a unique fingerprint.

Cite this