Efficient compilation techniques for large scale feature models

Feature modeling is used in generative programming and software product-line engineering to capture the common and variable properties of programs within an application domain. The translation of feature models to propositional logics enabled the use of reasoning systems, such as BDD engines, for the analysis and transformation of such models and interactive configurations. Unfortunately, the size of a BDD structure is highly sensitive to the variable ordering used in its construction and an inappropriately chosen ordering may prevent the translation of a feature model into a BDD representation of a tractable size. Finding an optimal order is NP-hard and has for long been addressed by using heuristics. We review existing general heuristics and heuristics from the hardware circuits domain and experimentally show that they are not effective in reducing the size of BDDs produced from feature models. Based on that analysis we introduce two new heuristics for compiling feature models to BDDs. We demonstrate the effectiveness of these heuristics using publicly available and automatically generated models. Our results are directly applicable in construction of feature modeling tools.