On the Benefits of Knowledge Compilation for Feature-Model Analyses

In practice, feature models often have up-to thousands of features and, thus, are typically infeasible to analyze manually. Hence, many different analyses have been proposed which often rely on multiple computationally complex computations, such as solving SAT or #SAT problems. Knowledge compilation is the process of compiling the original input into a computationally more advantageous format, such as BDDs. The upfront compilation effort is subsequently amortized by faster computations on the target format. In our work, we examine the benefits of applying knowledge compilation for feature-model analysis with three major contributions. First, we classify existing feature-model analyses regarding the underlying computational problems. Second, we perform a survey to collect available knowledge-compilation languages and inspect their capabilities with respect to the identified feature-model analyses. Third, we gather and empirically evaluate available knowledge compilers on industrial feature models.