Constraint programming heuristics for configuring optimal products in multi product lines

Nowadays, complex application domains require configuring multi-product lines where product features and constraints among them are specified in several variability models. These variability models are enriched with inter-model constraints representing the existing relations among domain concerns, and with non-functional properties modeled as attributes attached to product features. Multiple techniques use constraint programming to automate the cumbersome task of manually configuring a suitable product. Currently, there are some proposals to improve the performance of constraint solvers when configuring single-model product lines, however configuration scenarios with multiple interrelated and attributed models are not yet targeted. This paper proposes and evaluates three search heuristics used to configure optimal products regarding multi-objective criteria. Results are compared against the default search strategy of the Choco constraint solver. We evaluated the performance for configuring optimal products in four state-of-the-art product lines and 130 generated variability models representing multi-product lines that scale up to 6400 features and 960 constraints. As a result, we observe that the proposed heuristics perform better than the default solver strategy when the variability models scale in terms of features. In contrast, the default strategy and one of the proposed heuristics perform better as the number of interdependencies between variability models increases.