Genetic Algorithm and Variable neighbourhood search for BDD Variable Ordering Problem - Layeb, Abdesselem; Tabib, Nacer; Brirem, Bilel (INFOCOMP Journal of Computer Science, 2011)
The Binary Decision Diagram (BDD) is used to represent in symbolic manner a set of states. It is largely used in the field of formal checking. The variable ordering is a very important step in the BDD optimization process. A good order of variables will reduce considerably the size of a BDD. Unfortunately, the search for the best variables ordering has been showed NP-difficult. In this article, we propose a new iterative approach based on a hybrid Genetic Algorithm and Variable Neighborhood Search Algorithm. The obtained results are very encouraging and show the feasibility and effectiveness of the proposed hybrid approach.