Experimental and Theoretical Analysis of Local Search Optimising OBDD Variable Orderings

Thomas Jansen*, Christine Zarges

*Awdur cyfatebol y gwaith hwn

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion CynhadleddTrafodion Cynhadledd (Nid-Cyfnodolyn fathau)

Crynodeb

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.

Iaith wreiddiolSaesneg
TeitlEvolutionary Computation in Combinatorial Optimization
Is-deitl24th European Conference, EvoCOP 2024; Held as Part of EvoStar 2024; Aberystwyth, UK, April 3–5, 2024, Proceedings
GolygyddionThomas Stützle, Markus Wagner
CyhoeddwrSpringer Nature
Tudalennau177-192
ISBN (Electronig)978-3-031-57712-3
ISBN (Argraffiad)9783031577116
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 18 Ebr 2024
Digwyddiad24th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2024, held as part of EvoStar 2024 - Aberystwyth, Teyrnas Unedig Prydain Fawr a Gogledd Iwerddon
Hyd: 03 Ebr 202405 Ebr 2024

Cyfres gyhoeddiadau

EnwLecture Notes in Computer Science
Cyfrol14632

Cynhadledd

Cynhadledd24th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2024, held as part of EvoStar 2024
Gwlad/TiriogaethTeyrnas Unedig Prydain Fawr a Gogledd Iwerddon
DinasAberystwyth
Cyfnod03 Ebr 202405 Ebr 2024

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'Experimental and Theoretical Analysis of Local Search Optimising OBDD Variable Orderings'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn