A family of heuristic search algorithms for feature model optimization

Abstract

Feature models are a well-known formalism for capturing variability, commonalities and configuration rules of software systems. These models are a compact representation of the set of products in a software product line or configurations of a system at runtime, in terms of features and logical relationships among them. The feature model optimization problem consists of selecting a valid product from the model that satisfies a set of resource or business restrictions and optimizes an objective function commonly related to user preferences. This problem, although computationally intractable, has been addressed in several works with different algorithms. However, these approaches appeal to simplifications of the problem or present drawbacks that limit their application. For example, several approaches do not contemplate feature interactions, and some of them do not guarantee exact solutions or even valid solutions satisfying complex constraints. In this article, we propose a novel algorithm called CSA that overcomes the performance and common weaknesses of existing approaches. CSA can be parameterized with a set of classic search strategies (Backtracking, Branch & Bound, and Best-First Search) and heuristics that allow us to leverage solution optimality and search efficiency. This makes CSA appropriate for automating decisions both at design-time, where exact solutions are generally required, and at run-time, where selection must be done efficiently but sub-optimal solutions are acceptable. The algorithm supports different formats of objective functions, including multi-linear polynomial functions that are capable of representing feature interactions. We present an analysis to validate algorithm properties, and then a series of experiments with synthetic and real models to empirically compare CSA with existing alternatives to show the benefits of our approach. In our analysis, CSA showed to be complete, exact, and scalable for searching approximate solutions. The empirical results showed that the approximate variant of CSA can reach an optimality degree of 99%, against a 84% and 93% reached by other approximate alternatives based on genetic and greedy algorithms respectively. In terms of response time, CSA performed a 72% better than other approximate algorithms. Compared to other exact approaches, CSA improves response time on specific problem types. Furthermore, CSA was evaluated with problem instances involving feature interactions, showing that performance properties scale properly when the number of feature interactions increases.