Next-Generation Feature Models with Pseudo-Boolean SAT Solvers
Sebastian Henneberg · 2011
Feature models are an important artifact in software product line engineering. They describe commonality and variability of all product line members. This thesis proposes the use of attributes and additional constraints in feature modeling to extend expressiveness and usability. Therefore, new grammars were built to extend traditional feature models by optional integer attributes and additional constraints. We found a mapping that converts extended feature models into pseudo-boolean satisfiability (PBSAT) instances. This allows reasoning of feature models using a PBSAT solver. We took different feature model analysis operations from several authors to show applicability of the PBSAT representation. This required adaptations and led to extensions of known algorithms. We analyzed the scalability of our proposed adaptations by an evaluation of different real-world feature models.