Combining Multi-Objective Search and Constraint Solving for Configuring Large Software Product Lines

Software Product Line (SPL) feature selection involves the optimization of multiple objectives in a large and highly constrained search space. We introduce SATIBEA, that augments multi-objective search-based optimization with constraint solving to address this problem, evaluating it on five large real-world SPLs, ranging from 1,244 to 6,888 features with respect to three different solution quality indicators and two diversity metrics. The results indicate that SATIBEA statistically significantly outperforms the current state-of-the-art (p < 0.01) for all five SPLs on all three quality indicators and with maximal effect size (<(A)over tilde>(12) = 1.0). We also present results that demonstrate the importance of combining constraint solving with search-based optimization and the significant improvement SATIBEA produces over pure constraint solving. Finally, we demonstrate the scalability of SATIBEA: within less than half an hour, it finds thousands of constraint-satisfying optimized software products, even for the largest SPL considered in the literature to date.