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.