Feature models (FM) support the management of variability properties of software, products, and services. To enable feature model configuration, these models have to be translated into a corresponding formal representation (e.g., a satisfiability or constraint satisfaction representation). Specifically in interactive configuration, eficient response times are crucial. In this paper, we show how to improve the performance of constraint solvers (supporting FM configuration) on the basis of exploiting the concepts of collaborative filtering for recommending solver search heuristics (variable orderings and value orderings). As a basis for our recommendation approach, we used data (configurations) synthesized from real-world feature models using diferent state-of-the-art synthesis approaches. A performance analysis shows that, with heuristics recommendation, significant improvements of solver runtime performance compared to standard solver heuristics can be achieved. Feature models, configuration, constraint solving, search heuristics, performance optimization, collaborative filtering Feature models (FMs) are in wide-spread use for model- chine learning approach is the availability of training ∗Corresponding author.
1. Introduction ing variability properties [1, 2]. These properties can be translated into a formal representation [3] to support various types of reasoning tasks, for example, in the context of feature model analysis and feature model configuration. In this paper, we focus on the aspect of feature model configuration
where users of a configuration system define their preferences (e.g., in terms of intended feature inclusions) and the feature model configurator then tries to find a corresponding complete configuration which defines inclusion or exclusion for each feature.
Feature model configuration needs to be eficient which can become challenging specifically with large and complex configuration knowledge bases. The major means of improving the performance of solvers (specifically SAT and constraint solvers) is to employ diferent search heuristics which can help to cut down the search space as fast as possible. Following the idea of integrating machine learning (ML) with constraint solving [4], we propose to apply recommender systems [5], more specifically, collaborative filtering [ 6], to recommend solver nEvelop-O
0009-0005-0993-0911 (D. Garber)
The major contributions of this paper are the follow- each survey software configuration must include the
ing. (
The remainder of this paper is organized as follows. ible with ABtesting ( 8 ∶ ¬( ∧ )), the inIn Section 2, we provide an example feature model with clusion of ABtesting requires the inclusion of statistics the related constraint-based representation. In Section 3, ( 9 ∶ → ), and a basic license must we introduce an approach to collaborative filtering based not be combined with a multimedia answering mode recommendation of constraint solver search heuristics. ( 10 ∶ ¬( ∧ ) ).
In Section 4, we provide an overview of the synthesis Summarizing, our example feature model includes the approaches we have used in our recommendation set- list of (Boolean-valued) features (variables ) = { 1 ∶ tings. Performance evaluation results are summarized , 2 ∶ , 3 ∶ , 4 ∶ , 5 ∶ in Section 5. Threats to validity are discussed in Section , 6 ∶ , 7 ∶ , 8 ∶ , 9 ∶ 6. The paper is concluded with a discussion of future } . Furthermore, the model includes the set research issues in Section 7. of constraints = { 1.. 10}. These are the two major elements of an FM configuration task defined in terms of a constraint satisfaction problem (CSP) (see Definition 1).
is an assignIn the following, we introduce an example feature model representing the variability properties of a survey software (see Figure 1). Each configured survey software must have included a corresponding license model (which can be either advanced or basic). The features statistics and ABtesting are optional ones, i.e., must not be part of every configuration. Finally, each survey software conifguration must include a selected interaction mode (in terms of the type of questions (feature QA) supported) which consists of at least one out of question answering Definition 2 (FM Configuration). (feature basicQA) and multimedia based question answer- tion for an FM configuration task ( , , ) ing (feature multimediaQA).
The feature model in Figure 1 includes diferent relationships and cross-tree constraints ∈ . First, Definition 1 (FM Configuration Task). An FM conifguration task ( , , ) can be defined as a CSP, where V is a set of (Boolean-valued) variables = { 1, ..., } and = { 1.. } is a set of feature model constraints. Finally, = { 1.. } is a set of user requirements also represented in terms of constraints (mostly variable assignments).
2Without loss of generality, we focus on feature models and corresponding Boolean variable domains.
With a configuration task definition 2, we can introduce the concept of an FM configuration (Definition 2). ment = { 1 = 1 ∧ .. ∧ = } where ∪ ∪ (3) runtime (in ) to find the corresponding configurais consistent and every variable in has an assignment, tion (see Table 1). We use such entries to identify (reuse) i.e., we assume assignment completeness. search heuristics for completing new configuration tasks.
Assuming a set of defined user requirements = { 1 ∶ = , 2 ∶ = , 3 ∶ k-nearest neighbors (k=1). Table 1 shows a simpli = } (i.e., users do not need to define ifed example of how to apply ( nearest neighbor) their preferences with regard to all features) could re- based approaches for recommending search heuristics sult in the following complete configuration = for a new configuration task (in this example, we assume { = , = , = , = = 1 ). The table contains four (in our case synthesized) , = , = , = entries of complete configurations including further in , = , = } . formation on the used solver search heuristics, i.e, vari
Having introduced the concepts of a configuration able and variable value orderings. Finally, for each contask and a corresponding configuration, we are now able ifguration we have information about the corresponding to discuss our collaborative filtering based constraint solver runtime (in ). solver search heuristics recommendation approach in In this example, the new configuration task needs to more detail. be solved. The idea is to identify nearest neighbor conifgurations on the basis of the similarity between the new configuration task and the available (complete) 3. Collaborative Search Heuristics configuration entries ( 1 – 4 in Table 1). FollowRecommendation ing Formula 1 for determining the similarity between the new configuration task and each , configurations 1– 3 have the same similarity, i.e., (, 1) = (, 2) = (, 3) = 1.0.4 In this context, ′ denotes variables with associated specified user requirements, i.e., those variables of which have a corresponding initial value assignment in the configuration task definition (e.g., { 2, 4} in Table 1).
Our basic idea is to apply diferent types of nearest neighbor based collaborative filtering [ 6] for the purpose of recommending relevant solver search heuristics (including both, variable orderings (the order in which the solvers tries to instantiate variables) and variable value orderings also denoted as variable domain strategies (the order in which the solver instantiates variable values) for a new configuration task (see Definition 1).
Our used variable value orderings (i.e., variable do- (, ) =
main strategies) are highest first (H) and lowest first (L),
i.e., the constraint solver starts with trying to
instantiating the highest or the lowest variable value first. 3 For
the purposes of our experiments, we use diferent data
synthesis approaches [9] (see Section 4). Each entry of a
synthesized dataset represents a complete configuration
consistent with the constraints in and (see Definition
2). In addition to the feature settings (inclusion or
exclusion), each entry also includes information about (
(
In this context, task (the initial user requirements)
represents a partial configuration, since not every variable
needs to have an assigned value – assigned values are
assumed to represent user requirements ∈ .
k-nearest neighbors (k>1). The k-nearest neighbor
based approach identifies the most similar
configurations compared to the current configuration
(see Formula 1) and then chooses the configuration with
4( ,) denotes the value of variable .
the best solver runtime performance (which is then the
so-called nearest neighbor). Since 3 has the lowest
(best) runtime among the identified nearest neighbors, we
can reuse the solver search heuristics used to determine
3. If = 1 , only one nearest neighbor is identified and
the corresponding solver search heuristics are applied
to the current configuration task. The major diference
between = 1 and > 1 is that in > 1 settings it could
be the case that a configuration with lower similarity
(see Formula 1) is selected due to a better corresponding
runtime performance.
corresponding feature model. For each variable, a
corresponding variable value ordering heuristics has been
chosen randomly. Finally, we also chose a variable
ordering for variables not contained in the generated set
of user requirements . On the basis of this initial input
(randomly generated search heuristics and user
requirements), a solver has been activated with a repetition
factor of 5 to determine the average runtime needed to
solve the defined setting (see also Tables 2 and 3).
Following the overview of Pereira et al. [9], we have used
and evaluated the following data synthesis approaches.
5https://csrc.nist.gov/projects/automated-combinatorial-testing-forsoftware.
k-nearest neighbors (k>1, weighted). The previ- Random Sampling. Random Sampling is one of the
ously discussed k-nearest neighbor approach takes into most widely used methods to synthesize data for
configuaccount the similarity between the current configura- ration problems [15, 16, 17]. There are several variations
tion (task) and already existing configurations . In [9, 13] that can be diferentiated with regard to the
numour experiments, we were also interested in the impact ber generated samples. One of these variations generates
of taking into account tradeofs between configuration a fixed (pre-defined) number of configurations, regardless
similarity and solver runtimes (see Formula 2). of the properties of the underlying feature model. The
ifxed number approaches we have tested in the context
of our evaluation are: 100, 200, 500, 1000, 2000 and 10000.
(, ) = ( ) − ( ) (
4 2 4
Similar to the k-nearest neighbor based approach ( > 1), this weighted approach (see Formula 2) as well identiifes configurations similar to the current configuration (task), but then uses similarity as a weighting factor, i.e., not just selects the nearest neighbor with the best runtime performance. This way, we determine those nearest neighbors with a good runtime which are at the same as similar as possible to the given configuration task.
In Formula 2, we have introduced a small constant to avoid division by 0 which could happen in situations Heuristics Based Sampling. Other approaches are where the requirements in the given configuration task based on heuristics for configuration generation. are equivalent with the corresponding variable settings Feature Frequency Heuristic (FFH) The Feature Frein , i.e., the similarity is 1.0. Finally, we want to quency Heuristic (FFH) [18] generates configurations folmention that max(runtime) denotes the highest (global) lowing the strategy of ensuring that each feature occurs runtime value used to represent the worst (highest) run- at least a predefined times in the resulting configurations time observed in the (FM-specific) synthesized data. (corresponding thresholds can also be defined per feature). In our evaluation, we have applied the (global) 4. Used Data Synthesis feature-wise threshold values of 5, 10, and 20.
Feature Coverage Heuristic (FCH). FCH [19, 20, 18] tries Approaches to ensure the presence of every feature combination of size in the generated data. This approach could be applied in diferent ways, for example, by generating all possible -way feature combinations. We used the ACTS tool5 provided by [21], which generates so-called covering arrays [22]. This way, we generated data sets with 2-way and with 3-way coverage. Higher coverage comes at very high computational costs for larger models which forced us to omit corresponding synthetizations with our used ACTS tool [21].
Overall Synthesis Approach. The methods we chose for synthesizing configuration data are based on those discussed in Pereira et al. [9]. We have applied these synthesis approaches in our constraint solver search heuristics recommendation scenario for the purpose of generating complete and consistent configurations, i.e., each variable has a corresponding assignment and all assignments are consistent with the constraints in . As solver input, we have generated a set of user requirements ∈ representing around 10% of the features contained in the
Linux k = 5
Overall Evaluation Approach.
On the basis of the discussed data synthesis and recommendations, we now present the results of a performance evaluation. We have compared solver runtimes with default solver settings with our recommendation based approaches. For the standard setting, we have measured the time needed by the solver to find a solution (see Formula 3). 1) search heuristics recommendations. In this context, the constraint solver performance of diferent feature models has been evaluated. Compared to standard solver runtimes (without heuristics recommendations – see Table 4)) , we can observe significant corresponding runtime improvements. Values in bold indicate the best configuration synthesis strategy, values with a grey background the best corresponding value. Constraint solver performance with k-nearest neighbor based search heuristics recommendations (following the nearest neighbor selection approach of Formula 2). Again, the constraint solver performance of diferent feature models has been evaluated. Using this approach, we can observe further solver runtime improvements compared to the basic k-nearest neighbor based approach. Note that for = 1 the performance values are the same as in Table 2 due to the fact that the same heuristics are selected in this case. 150 test configuration tasks. In addition, to avoid biases (3) in the training data set, we have generated 5 training datasets for the mentioned settings. With this, we have measured the average runtime needed for solving the configuration task (see also Formulae 3 – 4). (4)
Comparison of Synthesis Strategies. Independent of the used synthesis strategy, solver performance can be 6See github.com/diverso-lab/benchmarking [13] and the S.P.L.O.T. repository [14]. 7See choco-solver.org. significantly improved with search heuristics recommendation, for example, in the context of the Linux feature model (see Table 4), runtimes can be reduced by half.
The analysis of the diferent data synthesis approaches showed that approaches generating smaller datasets in general perform best which can partially explained by the fact that the efort of determining nearest neighbors is reduced. The best performing synthesis approach for small models (REAL-FM-11 Model and MobileMedia Model) is Feature Coverage Heuristic (2-way) – due to computa- 7. Conclusions tional overheads, evaluations for larger models have been omitted. For the remaining settings, in the majority of In this paper, we have presented an approach to recomthe cases the best performing synthesis approach is the mend constraint solver search heuristics (variable orderFeature Frequency Heuristic (FFH) with threshold = 5 . ings as well as variable values orderings) which help to improve the performance of constraint solver based Comparison of K-Nearest Neighbor Approaches. feature model configuration. We have applied and comWhen comparing k-nearest neighbor and weighted k- bined diferent types of data synthesis strategies and cornearest neighbor based heuristics recommendation, we responding collaborative recommendation approaches can observe that both approaches result in a similar solver which have been used as a basis for recommending search performance, however, weighted k-nearest neighbor ap- heuristics for new feature model configuration tasks. The pears to be the more stable approach which is less sus- results of our performance evaluation show that an apceptible to outliers (in terms of low solver performance). proach to the recommendation of search heuristics combined with a well-fitted data synthesis approach can lead Comparison of -Values. When comparing diferent to significant performance improvements in feature con -values, we can observe a tendency that more complex ifguration (in our evaluation settings, we could observe feature models (and corresponding constraint satisfaction significant performance improvements of around 50% problems) tend to perform better with increasing -sizes. (and more) compared to standard solver runtimes). Major This can be partially explained by the fact that larger issues for future work are the evaluation of our approach models (with larger configuration/solution spaces) need in further domains (e.g., operating systems optimization) a higher k-value for achieving a certain coverage of the and the development/inclusion of model-based recomsearch space. On the other hand, the additional eforts to mendation approaches. be taken into account for increasing k-sizes (e.g., in terms of additional eforts in nearest neighbor determination) can to some extent be compensated by higher-quality References variable (value) ordering heuristics.
The major objective of the presented work is constraint solver optimization, however, the presented approach could also be applied in other application domains such as operating system optimization and the optimization of production schedules. We regard corresponding evaluations as a major focus of our future work. We are aware of the variety of FM knowledge representations – not all of these representations will directly profit from the concepts presented in this paper (since we focused on specific constraint solver heuristics). On the one hand, we regard related developments, i.e., learning other types of search heuristics, as a major focus of future research.
On the other hand, we want to emphasize that the presented collaborative recommendation approaches can be applied as such in other settings with a focus on the reuse of reasoning knowledge. We want to emphasize that we intentionally focused on comparing (memory-based) collaborative recommendation approaches. Future work will include evaluations with model-based (e.g., neural networks) collaborative recommendation approaches. Finally, we are also aware of diferent types of parallelization approaches helping the improve search eficiency (see, for example, [23, 24]). We regard a direct comparison with such approaches a major task for future work. bility Study, Technical Report, SEI, Carnegie Mellon per Variants That Meet Constraints, in: 12th InUniversity, Pittsburgh, PA, USA, 1990. ternational Workshop on Variability Modelling of [3] D. Benavides, P. Trinidad, A. Ruiz-Cortés, Au- Software-Intensive Systems, ACM, 2018, p. 83–88. tomated reasoning on feature models, in: [16] A. Grebhahn, C. Rodrigo, N. Siegmund, F. Gaspar, CAiSE’05, Springer-Verlag, Berlin, Heidelberg, 2005, S. Apel, Performance-influence models of multigrid p. 491–503. methods: A case study on triangular grids, Concur[4] A. Popescu, S. Polat-Erdeniz, A. Felfernig, M. Uta, , rency and Computation: Practice and Experience M. Atas, V. Le, K. Pilsl, M. Enzelsberger, T. Tran, An 29 (2017).
Overview of Machine Learning Techniques in Con- [17] J. Guo, K. Czarnecki, S. Apel, N. Siegmund, Wąstraint Solving, Journal of Intelligent Information sowski, Variability-aware performance prediction: Systems 58 (2022) 91–118. A statistical learning approach, in: 28th IEEE/ACM [5] A. Falkner, A. Felfernig, A. Haag, Recommenda- International Conference on Automated Software tion Technologies for Configurable Products, AI Engineering, ASE ’13, IEEE Press, Silicon Valley, Magazine 32 (2011) 99–108. CA, USA, 2013, pp. 301–311. [6] M. Ekstrand, J. Riedl, J. Konstan, Collaborative fil- [18] A. Sarkar, J. Guo, N. Siegmund, S. Apel, K. Czartering recommender systems, Found. Trends Hum.- necki, Cost-eficient sampling for performance preComput. Interact. 4 (2011) 81–173. diction of configurable systems, in: 30th IEEE/ACM [7] K. Meel, Counting, Sampling, and Synthesis: The International Conference on Automated Software Quest for Scalability, in: IJCAI-22, 2022, pp. Engineering, ASE ’15, IEEE Press, Lincoln, Ne5816–5820. braska, 2015, pp. 342–352. [8] J. A. Pereira, M. Acher, H. Martin, J. Jézéquel, Sam- [19] C. Kaltenecker, A. Grebhahn, N. Siegmund, J. Guo, pling efect on performance prediction of config- S. Apel, Distance-based sampling of software conurable systems: A case study, in: ACM/SPEC Inter- ifguration spaces, in: 2019 IEEE/ACM 41st Innational Conference on Performance Engineering, ternational Conference on Software Engineering ICPE ’20, ACM, 2020, p. 277–288. (ICSE), IEEE, Montrea, Quebec, Canada, 2019, pp. [9] J. A. Pereira, M. Acher, H. Martin, J. Jézéquel, G. Bot- 1084–1094.
terweck, A. Ventresque, Learning software con- [20] M. Lillack, J. Müller, U. Eisenecker, Improved ifguration spaces: A systematic literature review, prediction of non-functional properties in softJournal of Systems and Software 182 (2021) 111044. ware product lines with domain context, in: [10] S. Polat-Erdeniz, A. Felfernig, R. Samer, M. Atas, S. Kowalewski, B. Rumpe (Eds.), Software EngiMatrix factorization based heuristics for constraint- neering 2013, Gesellschaft für Informatik e.V., Bonn, based recommenders, in: 34th ACM/SIGAPP Sym- 2013, pp. 185–198. posium on Applied Computing (SAC ’19), ACM, [21] L. Yu, Y. Lei, R. Kacker, D. Kuhn, Acts: A combinatoLimassol, Cyprus, 2019, pp. 1655–1662. rial test generation tool, in: 6th IEEE International [11] M. Uta, A. Felfernig, D. Helic, V. Le, Accuracy- and Conference on Software Testing, Verification and consistency-aware recommendation of configura- Validation, IEEE, Luxembourg, 2013, pp. 370–375. tions, in: ACM International Systems and Software [22] C. Colbourn, Combinatorial Aspects of Covering Product Line Conference (SPLC’22), ACM, Graz, Arrays, Le Matematiche 59 (2004) 125–172.
Austria, 2022, pp. 79–84. [23] L. Bordeaux, Y. Hamadi, H. Samulowitz, Experi[12] V. Le, A. Felfernig, M. Uta, T. Tran, C. Vidal, Wipe- ments with Massively Parallel Constraint Solving, OutR: Automated Redundancy Detection for Fea- in: IJCAI’09, Morgan Kaufmann Publishers Inc., San ture Models, in: 26th ACM International Systems Francisco, CA, USA, 2009, pp. 443–448. and Software Product Line Conference, ACM, 2022, [24] V. Le and C. Vidal Silva and A. Felfernig and D. Bepp. 164–169. navides and J. Galindo and T.N.T. Tran, FastDiagP: [13] R. Heradio, D. Fernandez-Amoros, J. J. Galindo, An Algorithm for Parallelized Direct Diagnosis, in: D. Benavides, D. Batory, Uniform and scalable sam- AAAI’23, 2023, pp. 6442–6449. pling of highly configurable systems, Empirical
Software Engineering 27 (2022) 1–34. [14] M. Mendonca, M. Branco, D. Cowan, S.P.L.O.T.:
Software Product Lines Online Tools, in: 24th ACM SIGPLAN Conference Companion on Object Oriented Programming Systems Languages and Applications, OOPSLA ’09, ACM, 2009, pp. 761–762. [15] M. Acher, P. Temple, J.-M. Jézéquel, J. Galindo,
J. Martinez, T. Ziadi, VaryLATEX: Learning Pa