Technical Report No. 79, April 1996 - Abstract

Rolf Drechsler, Nicole Göckel, Bernd Becker:
Learning Heuristics for OBDD Minimization by Evolutionary Algorithms

Ordered Binary Decision Diagrams (OBDD) are the state-of-the-art data structure in CAD for ICs. OBDDs are very sensitive to the chosen variable ordering, i. e. the size may vary from linear to exponential.

In this paper we present an Evolutionary Algorithm (EA) that learns good heuristics for OBDD minimization starting from a given set of basic operations. The difference to other previous approaches to OBDD minimization is that the EA does not solve the problem directly. Instead, it developes strategies for solving the problem.

To demonstrate the efficiency of our approach experimental results are given. The newly developed heuristics are more efficient than other previously presented methods.