Variable ordering for shared binary decision diagrams targeting node count and path length optimisation using particle swarm technique

摘要

This study presents a particle swarm optimisation (PSO)-based approach to optimise node count and path length of the binary decision diagram (BDD) representation of Boolean function. The optimisation is achieved by identifying a good ordering of the input variables of the function. This affects the structure of the resulting BDD. Both node count and longest path length of the shared BDDs using the identified input ordering are found to be much superior to the existing results. The improvements are more prominent for larger benchmarks. The PSO parameters have been tuned suitably to explore a large search space within a reasonable computation time.