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
Subtitle of host publication24th European Conference, EvoCOP 2024; Held as Part of EvoStar 2024; Aberystwyth, UK, April 3–5, 2024, Proceedings
EditorsThomas Stützle, Markus Wagner
PublisherSpringer Nature
Pages177-192
Number of pages16
ISBN (Print)9783031577116
DOIs
Publication statusPublished - 2024
Event24th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2024, held as part of EvoStar 2024 - Aberystwyth, United Kingdom of Great Britain and Northern Ireland
Duration: 03 Apr 202405 Apr 2024

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14632 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2024, held as part of EvoStar 2024
Country/TerritoryUnited Kingdom of Great Britain and Northern Ireland
CityAberystwyth
Period03 Apr 202405 Apr 2024

Keywords

  • local search
  • OBDD variable ordering
  • run time analysis

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