Heuristics to Optimize the Variable Ordering in Binary Decision Diagrams

Seminar paper from the year 2019 in the subject Computer Science - Commercial Information Technology, grade: 1,0, University of Kaiserslautern, language: English, abstract: In this paper, two fault trees are examined, for which five heuristics are applied to evaluate and compare their effectiveness. The arrangement of variables in a Binary Decision Diagram (BDD) determines the size of the BDD after applying reduction rules and thus plays a decisive role in finding a compact representation of the Boolean function. Since there are already many possible arrangements with only a few variables and techniques for finding the optimal solution requiring too much time, the use of heuristics is needed. The main focus is on known approaches and especially on the dynamic method of the sifting algorithm.