SAT-based analysis of feature models is easy

TLDR

Feature models are a widely used variability modeling notation in product line engineering, and their automated analyses typically translate models to propositional logic for SAT solvers, with reported efficiencies. The authors aim to generalize and quantify previous efficiency studies of SAT‑based feature model analyses. They accomplish this through a series of independent experiments. The experiments demonstrate that SAT‑based analyses of realistic feature models are consistently efficient across all realistic instances, with no phase transition observed, encouraging further development of such methods.

Abstract

Feature models are a popular variability modeling notation used in product line engineering. Automated analyses of feature models, such as consistency checking and interactive or offline product selection, often rely on translating models to propositional logic and using satisfiability (SAT) solvers.Efficiency of individual satisfiability-based analyses has been reported previously. We generalize and quantify these studies with a series of independent experiments. We show that previously reported efficiency is not incidental. Unlike with the general SAT instances, which fall into easy and hard classes, the instances induced by feature modeling are easy throughout the spectrum of realistic models. In particular, the phenomenon of phase transition is not observed for realistic feature models.Our main practical conclusion is a general encouragement for researchers to continued development of SAT-based methods to further exploit this efficiency in future.