=Paper=
{{Paper
|id=Vol-2220/12_CONFWS18_paper_15
|storemode=property
|title=Generating Configuration Models from Requirements to Assist in Product Management – Dependency Engine and its Performance Assessment
|pdfUrl=https://ceur-ws.org/Vol-2220/12_CONFWS18_paper_15.pdf
|volume=Vol-2220
|authors=Juha Tiihonen,Iivo Raitahila,Mikko Raatikainen,Alexander Felfernig,Tomi Männistö
|dblpUrl=https://dblp.org/rec/conf/confws/TiihonenRRFM18
}}
==Generating Configuration Models from Requirements to Assist in Product Management – Dependency Engine and its Performance Assessment==
https://ceur-ws.org/Vol-2220/12_CONFWS18_paper_15.pdf
Generating Configuration Models
from Requirements to Assist in Product Management –
Dependency Engine and its Performance Assessment
Juha Tiihonen1 and Iivo Raitahila1 and Mikko Raatikainen1 and Alexander Felfernig2 and
Tomi Männistö1
Abstract. Requirements engineering is often, especially in the con- ments to be implemented simultaneously might need to follow all
text of major open source software projects, performed with issue dependencies transitively, which is not readily supported by the is-
tracking systems such as Jira or Bugzilla. Issues include require- sue trackers. The issue trackers are not either necessarily optimal for
ments expressed as bug reports, feature requests, etc. Such systems the concerns of product or release management that need to deal with
are at their best at managing individual requirements life-cycle. The different requirement options, alternatives and constraints, as well as
management of dependencies between issues and holistic analysis their dependency consequences when deciding what to do or not to
of the whole product or a release plan is usually scantly supported. do. However, dependencies in general are found to be one of the key
Feature modeling is an established way to represent dependencies concerns that need to be taken into account, e.g., in requirements pri-
between individual features, especially in the context of Software oritization [1, 9, 18] and release planning [2, 17]. In fact, the above
Product Lines — well-researched feature model analysis and con- concerns are not at the core of issue trackers’ support for the require-
figuration techniques exist. We developed a proof-of-concept depen- ments engineering activity. Rather, issue trackers focus more on a
dency engine for holistically managing requirements. It is based on single issue, its properties, and its life cycle. The situation is not nec-
automatically mapping requirements and their dependencies into a essarily specific only for issue trackers, but it exists also in other
variant of feature models, enabling utilization of existing research. kinds of RMS.
The feature models are further mapped into a constraint satisfaction In the context of a Horizon 2020 project called OpenReq, we de-
problem. The user can experiment with different configurations of veloped a proof-of-concept Dependency Engine for holistically man-
requirements. The system maintains the consistency of dependencies aging requirements as a single model. It is based on automatically
and resource constraints. To evaluate the feasibility of the system, we mapping requirements and their existing isolated dependencies into
measure the performance of the system both with some real and gen- the Kumbang [3] variant of feature models, enabling utilization ex-
erated requirements. Despite some remaining performance issues, it isting research. A feature model is further mapped into a constraint
seems that the approach can scale into managing the requirements of satisfaction problem. The user can experiment with different config-
large software projects. urations of requirements. The system maintains the consistency of
dependencies and resource constraints.
This paper outlines the principle of the Dependency Engine and
1 INTRODUCTION
addresses its feasibility in terms of performance. We measure the
There are various kinds of requirement management systems (RMS) performance of the system both with some real and generated re-
applied in requirements engineering [10]. In particular, different is- quirements. Responsive performance is important for interactive us-
sue tracker systems, in which requirements are captured as issues, age, e.g., what-if analysis of requirements to include in a release.
are becoming increasingly popular, especially in large-scale, glob- Furthermore, it is important that decisions are based on current in-
ally distributed open source projects, such as in the cases of Bugzilla formation; either relatively fast model generation or a way to update
for Linux Kernel, Github tracker for Homebrew, and Jira for Qt. An models ’on-the-fly’ are required.
issue tracker can contain tens of thousands requirements, bugs and The rest of the paper is organized as follows. Section 2 outlines
other items that are different ways interdependent from each other. the concept of a feature model. Section 3 presents the research ques-
Issue tracker systems as RMSs provide primarily with support tions, general idea of the Dependency Engine, applied data and tests.
for individual requirements throughout various requirements engi- Section 4 presents the results, Section 5 provides analysis and dis-
neering activities, such as requirements documentation, analysis, and cussion. Finally, Section 6 concludes.
management as well as tracking the status of a requirement over its
life cycle. Even though individual dependencies, including more ad-
vanced constraints, can be expressed in the case of an individual re- 2 BACKGROUND: FEATURE MODELING
quirement, more advanced analysis over all requirements of a system
The notion of a feature model, similarly as a requirement, is not un-
taking into account the dependencies and properties of the require-
ambiguous. A feature of a feature model is defined, e.g., as a char-
ments is not well supported. For example, deciding a set of require-
acteristic of a system that is visible to the end user [12], or a system
1 University of Helsinki, Finland, first.last@helsinki.fi property that is relevant to some stakeholder and is used to capture
2 Graz University of Technology, Austria, alexander.felfernig@ist.tugraz.at
commonalities or discriminate among product variants [8]. A feature
model is a model of features typically organized in a tree-structure.
One feature is the root feature and all other features are then the
subfeatures of the root or another feature. Additional relationships
are expressed by cross-branch constraints of different types, such as
requires or excludes. Feature model dialects are not always precise
about their semantics, such as whether the tree constitutes a part-of
or an is-a structure [19]. Despite this, feature models have also been
provided with various formalizations [8, 16] including a mapping to
constraint programming [5, 6].
Specifically, we apply the Kumbang feature model conceptualiza-
tion [3] as the basis. It has a textual feature modeling language and
it has been provided with formal semantics. Kumbang specifies sub-
features as part-of relations and allows defining separate is-a hier-
archies. Kumbang supports feature attributes and its constraint lan-
guage can be used to express cross-branch relationships.
A feature model is a variability model roughly meaning that there
are optional and alternative features to be selected, and attribute val-
ues to be set that are limited by predefined rules or constraints. When
variability is resolved, i.e., a product is derived or configured, the
result is a configuration. Variability is resolved by making configura-
tion selections such as an optional feature is selected to be included,
or one of alternatives is selected. A consistent configuration is a con-
figuration in which a set of selections have been made, and none of
the rules have been violated. A complete configuration is a consistent
configuration in which all necessary selections are made.
Feature modeling has become a well-researched method to man-
age variability and has been provided with several different analyses
to assist in system management [4]. Figure 1. Workflows of the Dependency Engine
3 METHODS AND DATA
Milla is a front-end that is used to access requirement data via
We follow Design Science in the sense that the aim is to innovate volatile or case-dependent interfaces. For example, it extracts re-
a novel intervention and bring it into a new environment so that the quirements via the API of Jira. It outputs MulSON, a JSON based
results have value in the environment in practice [11]. Dependency intermediate transfer format understood by Mulperi.
engine is the artifact of the intervention and this paper focuses on its Mulperi converts from a small number of stable requirement in-
quality attributes. The specific research questions are: put formats such as MulSON into the Kumbang feature modeling
language. It can generate a number of queries to SpringCaaS.
• RQ1: Can the OpenReq Dependency Engine scale to real-world
SpringCaaS takes as input Kumbang feature models and converts
projects?
them into a corresponding Constraint Satisfaction Problem (CSP).
• RQ2: How can the performance of the Dependency Engine be
Choco Open-Source Java library for Constraint Programming [15]
improved?
was selected because it is Java-based, popular, and has good per-
formance and a permissive license. The Kumbang model and corre-
3.1 Approach and architecture sponding the data structures are saved for subsequent use.
To facilitate requirement management via a feature-based approach,
we make each requirement correspond to exactly one feature. The 3.2 Potential bottlenecks and related tests
properties of a requirement correspond to the attributes of a feature.
Network and external system bottlenecks Jira integration
The dependencies of individual requirements are mapped to hierar-
fetches requirements from the RMS one requirement at a time
chies and constraints of a feature model. We currently rely only on
over network, which can potentially create performance bottlenecks.
the dependencies explicitly expressed in requirements although we
These bottlenecks are outside the scope of this paper4 .
will aim to extract missing dependencies with NLP technologies. In
order to make such a mapping, we need a feature model dialect that
is conceptually relatively expressive supporting feature typing and Requirement model generation Milla generates feature models
attributes. Kumbang was selected for this purpose. from requirements data fetched from Jira. Effectively, relevant data,
The Dependency Engine currently consists of three stand-alone such as IDs, dependencies and the attributes that are needed in infer-
software components with specific responsibilities: Milla, Mulperi ence, are extracted and a MulSON presentation is generated.
and SpringCaaS, see Figure 1. There are two different workflows:
creating a model from requirements data and making subsequently Feature model generation A requirement model expressed in
queries against the model. These three components operate as REST- MulSON is sent to Mulperi. Mulperi generates a feature model ex-
type services and are implemented using the Java Spring framework3 . pressed in the Kumbang feature modeling language. Mulperi’s func-
3 https://spring.io/ 4 Bottlenecks were identified and solved by adding parallel connections.
tionality is largely based on data structure manipulation - JSON input 3.3.2 Synthetic data
and Kumbang output. The transformation is straightforward. Mulperi
also saves the results into an in-memory database. This model is then The synthetic datasets were created and run using automated scripts.
sent to SpringCaaS in a single message. SynData1 dataset contains a total of 450 models with permutations
of the amounts of requirements (from 100 to 2000), a ’requires’ de-
pendency (from 0 to 75% of the requirements), an optional subfea-
Feature model to CSP A feature model expressed in Kumbang is
ture with one allowed feature (from 0 to 75% of the requirements)
parsed. Kumbang syntax resembles many programming languages.
and a number of attributes (from 0 to 5 per requirement); each at-
Therefore parsing is potentially heavy.
tribute has two possible values, e.g., 10 and 20.
Based on the data structures representing the feature model, a cor-
A smaller dataset (60 test cases), SynData2, was used for opti-
responding Constraint Satisfaction Problem (CSP) is generated. Ba-
mization tests with sum constraints, see Section 3.4.5. SynData2
sically, a set of Boolean CSP variables represents instances of indi-
contains models with permutations of the amounts of require-
vidual feature types. Each of these is related to corresponding integer
ments (from 100 to 2000), a ’requires’ dependency (from 0 to
CSP variables that represent attribute values of these individual fea-
75% of the requirements), no further subfeatures and 1 or 2 at-
tures. Enumerated strings are mapped to integers. Choco constraints
tributes with a fixed random value from 1 to 100. An example of
are created based on the dependencies; the constraints can access the
a SynData2requirement in MULSON format:
presence of a feature, and relationships between attribute values of
features. The current implementation supports only binary relation- {
"requirementId": "R4",
ships (requires, excludes). "relationships": [
{
In addition, it is possible to specify global resource (sum) con- "targetId": "R25",
"type": "requires"
straints over specific attributes. For example, the sum of efforts of }
included features can be constrained. To facilitate this, the imple- ],
"attributes": [
mentation reserves attribute value 0 to attribute values of features {
"name": "attribute1",
that are NOT in configuration. "values": ["9"],
"defaultValue": "9"
},{
"name": "attribute2",
CSP solving The prime suspect for performance bottlenecks is "values": ["22"],
"defaultValue": "22"
solving the CSP representing a model of requirements. There are a }
],
number of tasks to accomplish based on a constructed model. "name": "Synthetic requirement nro 4"
}
• check a configuration of features for consistency
• complete a configuration of features 3.4 Empirical tests
• determine the consequences of feature selections
3.4.1 Test setup
The selection of search strategy often has significant effect on
solvability and quality of solutions [15]. Measurements should be conducted when the software’s behaviour is
typical[13]. Since there is currently no production environment, the
tests are conducted on a development environment that closely re-
3.3 Data sembles the possible production environment. Furthermore, we aim
The performance evaluations are based both on real data from the Qt to perform tests that could correspond to real usage scenarios.
company and synthetic data. The test machine is an Intel Core i5-4300U 1.9GHz dual core lap-
top with 16GB of RAM and an SSD disk, running Ubuntu Linux
16.04 and a 64-bit version of Oracle Java 1.8.0. All software compo-
3.3.1 Real requirements nents except for Jira are run on the same machine.
Qt is a software development kit that consists of a software frame- The examined software components log execution times to files
work and its supporting tools that are targeted especially for cross- that are collected after each automated test run. A timeout was set to
platform mobile application, graphical user interface, and embedded limit the solving of Choco in SpringCaaS.
application development. All requirements and bugs of Qt are man- Although SpringCaaS is a single component, we often report the
aged in the Qt’s Jira5 that is publicly accessible. Jira6 is a widely used execution time in two parts: Choco Solver and the rest of Spring-
issue tracker that can contain many issue types and has a lot of func- CaaS. This is because often Choco’s solve operation takes the most
tionality for the management of issues. Issues and bugs can be con- time, but the initial tests showed that the Kumbang parser becomes a
sidered as requirements and they have dependencies and attributes bottleneck in specific situations.
with constant values, such as priority and status. Thus, known re-
quirements and their dependencies have already been identified and 3.4.2 Initial trials and initial search strategy
entered into Jira. Qt’s Jira contains 18 different projects and although
some of the projects are quite small and discontinued, QT-BUG as Initial testing was performed with the goal to complete a configura-
the largest project contains currently (April 2018) 66,709 issues. tion of requirements with a minimal number of additional require-
For empirical evaluation with real data, a set of issues was gath- ments. The pareto optimizer of Choco was applied to provide alter-
ered from Qt’s Jira and processed through the whole pipeline. Only native solutions7 . All features were included in the pareto front. By
well-documented requirements having dependencies were selected default, Choco uses the domOverW Deg search strategy for interger
to the dataset JiraData that contains 282 requirements. and Boolean variables [15]. Table 3 describes the search strategies
5 https://bugreports.qt.io 7 Pareto optimizer dynamically adds constraints: a solution must be strictly
6 https://www.atlassian.com/software/jira better than all previous solutions w.r.t. at least one objective variable [15].
applied. In our domain and way of modeling, the strategy effectively minDomLBSearch, see Table 3. These were augmented with
leads to selection of excessive number of features. This is contrary to bestBound, lastConf lict or both; e.g., bestBound adds directs
the initial goal. As results in the beginning of Section 4 will show, an search based on the objective function and a strict consistency check.
alternative search strategy was required to achieve satisfactory per-
formance. The Search Strategy was changed to minDomLBSearch; it Table 1. Resource constraints for optimization tests
is used in the rest of the tests unless otherwise mentioned.
Constraint# P Constraint
0 P attribute1 > 1000
3.4.3 Requirement model generation 1 P attribute1 = 1000
2 attribute1
P< 1000
JiraData and SynData1 Datasets were applied to run the whole P
pipeline from gathered requirements to a Kumbang textual model
3 P attribute1 > 1000 ∧ P attribute1 < 2000
4 attribute1 > 1000 ∧ attribute2 < 2000
and a serialized feature model. The process is illustrated at the left
hand side of Figure 1. The different steps were timed.
In the case of SynData1 dataset, Milla was bypassed because the
test cases were expressed directly in MULSON. Note that model gen- Table 2. Constraints, number of attributes and usage scenarios
eration includes finding a consistent configuration of features; this
search is performed as a form of a model sanity check. Constraint# #attributes Optimization goal
0, 1, 3 1 Simulate achieving desired utility with a
minimal number of requirements to imple-
3.4.4 Requirement configuration ment. Minimizes the number of require-
ments.
Autocompletion of configurations was performed with the 2 1 Check the consistency of a given partial
JiraData dataset. A run was performed with a sum calcula- configuration with respect to maximum ef-
tion constraint. Here, each requirement has a numerical priority fort and complete the configuration with
as few requirements as possible. Minimizes
attribute. The query instructed SpringCaaS to give a configuration the number of requirements. In the case of
where the sum of these priority attributes was greater than 100. SynData2, the test is redundant, only the
More substantially, requirement configuration was also performed root feature will be included.
with the SynData1 dataset to analyse the performance under vary- 4 1 (Not relevant, 2 attributes in constraint, 1 in
model)
ing number of requirements and their properties (attributes, depen-
0, 1, 2, 3 2 Simulate maximisation of utility under
dencies), and user-specified requirements. This test applies optimiza- resource constraint: Maximize sum of
tion to find a (close to) minimum configuration that includes pre- attribute2
selected features, if any. Effectively, the configuration of require- 4 2 Minimize the number of requirements to im-
ments is completed. This is presumably one of the computationally plement under constraints of minimum util-
ity and maximum effort.
most intensive operations. The configuration phase is tested in ten it-
erations: first selecting only one requirement and then increasing the
number of selected requirements by 10% so that the tenth iteration
has 1 + 90% requirements selected.
4 RESULTS
3.4.5 Optimised release configuration under resource The results of the initial trials are in the two first rows of Table 4. The
constraint timeout and solution limits were disabled. The processing time was
unacceptable, as reflected in the results.
We performed a number of resource-constrained optimization tests.
Here, we applied global sum (resource) constraints specified in Ta-
ble 1 to constrain the allowed solutions. SynData2 Dataset contains
4.1 Requirement model generation
test cases with 1 or 2 attributes per requirement (see Section 3.3.2). The first two rows of Table 6 present the results of processing the
Effectively, the combination of number of attributes and the applied JiraData dataset through the whole pipeline. Table 5 shows the re-
constraint correspond to usage scenarios presented in Table 2. Fi- sults of processing the SynData1 dataset. A save operation includes
nally, we applied the bestBound(minDomLBSearch()) search finding a consistent non-optimized configuration of requirements.
strategy, after we had experimented with different alternatives, see Figure 2 presents cases with 1000 requirements. Each bar color
Section 3.4.6 and corresponding results. corresponds to a test case with a specific number of dependencies
We run the tests with 60s, 10s and 3s timeout values to see the (from 0 to 200) and subfeatures (from 200 to 1000). The elapsed
effect of allowed time on the solvability and to get an impression on time in Mulperi, SpringCaaS and Choco are shown for 0, 2000 and
the quality of solutions. In addition, we developed and experimented 5000 attributes, that is, 0, 2 or 5 attributes per feature, each with two
with a custom algorithm that (roughly) first ’filled’ effort bounds with possible values per requirement.
’big’ features and used ’small’ ones to meet the bound. Figure 3 depicts a case with 1000 requirements and different num-
ber of subfeatures (a requirement can be a subfeature of many re-
quirements). Please note the logarithmic scale. With 5000 subfea-
3.4.6 Determining search strategy
tures it took over five hours to parse the model.
We tested a set of different search strategies for performance, Starting from (some) models with 1000 requirements, the serial-
utilizing the 2000 requirement test cases of the SynData2 ization of the parsed Kumbang model failed due to a stack overflow
dataset. The experimented basic search strategies included error. It was necessary to increase the Java Virtual Machines stack
activityBasedSearch, Choco default domOverW Deg, and size to one gigabyte to prevent out-of-memory errors.
Table 4. Effect of search strategy with Pareto optimizer, JiraData dataset
Strategy Optional features Mandatory features Attributes Solutions Time
default 14 0 0 60 130 to 300 ms
default 20 0 0 1046 11600 to 11900 ms (unacceptable)
minDomLBSearch 14 0 0 1 120 to 170 ms
minDomLBSearch 20 0 0 1 150 to 190 ms
minDomLBSearch 235 0 2 per feature 1 160 to 200 ms
minDomLBSearch 118 117 2 per feature 1 400 to 650 ms
Table 5. Minimum, maximum and median test cases of the save phase, SynData1 dataset
Requirements Dependencies Subfeatures Attributes Mulperi time (ms) SpringCaaS time (ms) Choco time (ms) Total time (ms)
500 375 200 0 85 158 98 341
500 50 500 1000 504 247 493 1244
500 250 500 2500 1971 439 2133 4543
750 563 150 0 159 220 401 780
750 375 0 1500 1040 371 2239 3650
750 563 1125 3750 4988 684 6359 12031
1000 750 400 0 309 347 670 1326
1000 750 0 2000 1895 584 4144 6623
1000 750 1500 5000 8859 1029 12772 22660
1500 1125 600 0 584 509 2009 3102
1500 0 1500 3000 4942 733 8756 14431
1500 750 2250 7500 21747 1738 30270 53755
2000 1000 800 0 661 566 4781 6008
2000 1500 0 4000 6958 1079 15816 23853
2000 1500 2000 10000 37692 2018 46433 86143
Table 3. Choco Search strategies
Search strategy Description
activityBasedSearch Search strategy for ”black-box” constraint solving.
” ... the idea of using the activity of variables during
propagation to guide the search. A variable activ-
ity is incremented every time the propagation step
filters its domain and is aged.”[14]. Used parame-
ters (GAMMA=0.999d, DELTA=0.2d, ALPHA=8,
RESTART=1.1d, FORCE SAMPLING=1) [15] Figure 2. Performance effect of attributes
domOverWDeg Choco default. ”Intuitively, it avoids some trashing
by first instantiating variables involved in the con-
straints that have frequently participated in dead-
end situations” [7]. Slightly oversimplifying, the
strategy attempts to solve hard parts of a CSP
first, weighting constraints by their participation in
dead-ends.
minDomLBSearch ”Assigns the non-instantiated variable of smallest
domain size to its lower bound” [15]
bestBound Search heuristic combined with a constraint per-
forming strong consistency on the next decision
variable and branching on the value with the best
objective bound (for optimization) and branches on
the lower bound for SAT problems.[15]
lastConflict ”Use the last conflict heuristic as a plugin to im-
prove a former search heuristic Should be set after
specifying a search strategy.”[15]
Figure 3. Kumbang parser’s fatigue
Table 6. Measurements from the whole pipeline, JiraData dataset
Function Requirements Request Milla time Mulperi time SpringCaaS time
Save model 1 - 0,182 s 0,010 s 0,050 s
Save model 282 - 1,252 s 0,311 s 0,315 s
Configure 1 empty - 0,050 s 0,005 s
Configure 282 empty - 0,050 s 0,143 s
Configure 282 10 features - 0,040 s 0,172 s
Configure 282 25 features - 0,077 s 0,127 s
Configure 282 50 features - 0,116 s 0,099 s
Configure 282 10 features with dependencies - 0,040 s 0,093 s
Configure 282 sum calculation constraint - - 5,098 s (timeout)
Table 7. Minimum, maximum and median test cases of the configuration phase, SynData1 dataset
Requirements Dependencies Subfeatures Attributes Requirements in request Mulperi (ms) SpringCaaS (ms) Choco (ms) Total (ms)
100 10 0 0 1 9 10 4 23
100 10 20 200 91 10 21 8 39
100 0 0 500 1 27 54 14 95
500 0 100 0 451 34 79 19 132
500 100 200 0 101 33 61 71 165
500 0 0 2500 201 34 266 549 849
750 0 150 0 601 60 122 55 237
750 0 150 1500 376 63 156 344 563
750 375 0 3750 601 70 273 1614 1957
1000 750 1000 0 1 129 133 126 388
1000 500 0 2000 401 90 252 777 1119
1000 0 0 0 1 1344 414 1788 3546
1500 0 0 0 1351 186 363 179 728
1500 0 0 3000 751 185 364 2159 2708
1500 300 0 7500 1351 263 715 9087 10065
2000 0 0 0 1801 237 619 334 1190
2000 200 0 4000 801 297 515 4445 5257
2000 1000 0 10000 1801 573 1056 16464 18093
Figure 4. Performance effect of dependencies, 1500 requirements
Figure 5. Performance effect of selected requirements and unselected
attributes
4.2 Requirement configuration
4.3 Optimized configuration under resource
The results of the configuration task with the JiraData dataset are constraint
from row 3 onwards in Table 6. In case of the sum constraint (the last
row), SpringCaaS was able to find 107 to 120 solutions before the Table 8 presents a summary of the results of test that minimize the
timeout at 5s was reached. number of features. Note that constraint #4 is from test cases with 2
Table 7 contains the minimum, maximum and median measure- attributes, the others apply to test cases that have one attribute that
ments of total execution times for varying numbers of requirements, is constrained. Because all features are optional, tests with constraint
dependencies, subfeatures, attributes and number of pre-selected re- #1 trivially contain only the root feature of the model.
quirements in the request. Table 9 represents the results of optimizing via Maximization of
Figure 4 shows the effect of the number of dependencies in case the sum of attribute 2 (e.g. utility) under constraints on attribute1.
of 1500 requirements per test case, but with a varying number of Test cases with 100, 500, 750, 1000, 1500 and 2000 requirements
requires-dependencies. and varying numbers of requirements are solvable with 60s timeout.
Figure 5 shows the effect of the number of requirements and at- 10s handles all cases except 2000 requirements. 3s timeout is only
tributes in case of 1500 and 2000 requirements per test case. applicable to cases with 100, 500 and 750 requirements.
Table 8. Minimization of the number of features. Results of 60 second timeout compared with 10 and 3 second timeouts and the custom algorithm. Lower
number of features in a solution is better. T est: the type of the testcases, #a: the number of attributes in the test cases. N : the average number of features in
the minimal solution found with the 60s timeout. N=10 : the number of test cases where 10s timeout search finds the same number of features than the 60s
version. N>10 : the number of test cases where 10s timeout search includes a larger number of features than the 60s version. ∆N10 : the average number of
additional features included in a solution found with 10s timeout when compared to the 60s search. ∆N10 (%): the average percentage of additional included
features found by the 10s version. N=3 , N>3 , ∆N3 , ∆N3 (%): 3 second timeout versions analogously as 10s. The corresponding figures of the custom
algorithm are presented similarly: N=c , Nc , ∆Nc (%). Note that N10 ∆N10 ∆N10 (%) N=3 N>3 ∆ N3 ∆N3 (%) N=c Nc ∆Nc (%)
0 1 14.3 14 11 0.48 3.38% 7 8 0.60 4.92% 4 7 19 2573.33%
1 1 14.3 14 11 0.52 3.63% 7 8 0.67 4.92% 6 4 20 106.67%
2 1 1.0 25 0 0.00 0.00% 15 0 0.00 0.00% 30 0 0 0.00%
3 1 14.3 13 12 0.52 3.65% 7 8 0.73 4.92% 4 7 19 620.00%
4 2 14.4 17 8 0.32 2.26% 6 9 0.67 4.40% 0 0 30 1456.67%
A memory of 3 GB was required to complete the tests. The Requirement model generation The number of dependencies be-
bestBound search strategy became feasible by applying the opti- tween the requirements seem to have no impact during the save
mization to one variable or to the sums of attributes. A pareto front phase. To avoid out-of memory errors, Kumbang model read and
with all feature variables caused excessive memory consumption. write methods could be overridden with an implementation that suits
better for the Kumbang data structure, or the serialization phase
4.4 Determining search strategy could be omitted altogether. On the other hand, optimized solving
needs even more memory.
Table 10 compares search strategies with 2000 require- Increasing the number of attributes increases the processing time
ment test cases and minimization tasks. def aultSearch and of each component steadily, see Figure 2. Increasing the amount
activityBasedSearch fail in a number of cases with 60s timeout.8 of subfeatures increases the processing time of Mulperi and Choco
minDomLBSearch can solve all these cases. Negative ∆N steadily as well, but when the amount of subfeatures is very large,
indicates that the compared search strategy found better solutions the Kumbang parser slows down drastically, see Figure 3.
(e.g. Total number of features was 18 less in the 30 tests) .
Constraint #2 with 2 attributes is essentially uncon-
Requirement configuration The results in Section 3.4.4 suggest
strained for big problems. Here, the optimal solution in-
that a five second timeout would be sufficient for models with about
cludes all features. Plain minDomLBSearch fails to
500 requirements or less. The configuration of all 1000 requirement
’notice’ that. Both bestBound(minDomLBSearch())
models and most of the 1500 requirement models can be performed
and lastConf lict(bestBound(minDomLBSearch()))
in less than five seconds.
help the solver to find the maximal solution. Of
The timeout value of the save phase could be set to be longer. Both
these, in terms of maximized result on attribute2,
timeout values could be controlled with parameters, for example if
bestBound(minDomLBSearch()) is slightly better in 3
the user thinks that he/she can wait for a full minute for the process-
cases and lastConf lict(bestBound(minDomLBSearch())) in
ing to complete. During the configuration phase, the dependencies
one. Due to limitations of space, further details are omitted.
actually ease Choco’s inference burden. Figure 4 with 1500 require-
Earlier tests with all features in the pareto front prevented the us-
ments shows that when there are no dependencies, the preselected
age of bestBound strategy due to increased memory consumption.
requirements in the configuration request speed up Choco linearly.
The increase in configuration request size adds processing over-
Table 10. Comparison of search strategies with 2000 requirement cases head to SpringCaaS. Secondly, when the dependency rate gets
and Minimization tasks with 60s timeout
Search Strategy # no so- ∆N higher, more requirements are included in the configuration early on,
lution again helping Choco perform faster. The same is true for subfeatures:
minDomLBSearch() 0 0
lastConf lict(minDomLBSearch()) 0 -12 selecting requirements with subfeatures decreases processing time.
bestBound(minDomLBSearch()) 0 -18 With attributes, the situation is the opposite. The more there are
lastConf lict(bestBound(minDomLBSearch())) 0 -18
def aultSearch() 20 attributes and the more configuration request contains selected re-
bestBound(def aultSearch()) 45 quirements, the more time it takes to select attributes, see Figure 5.
activityBasedSearch() 50
bestBound(activityBasedSearch()) 49 The optimization task is computationally intensive. It is difficult
lastConf lict(bestBound(activityBasedSearch())) 49
for the solver to determine if an optimal solution has been found.
Therefore solving practically always ends with a timeout.
Optimised release configuration under resource constraint
5 ANALYSIS AND DISCUSSION
When a solution is found, the versions with a lower timeout value
Initial trials The results of Table 4 turned out to be too good: remain almost as good as solutions obtained with 60s timeout. The
it happens that the minimal requirement configurations of models in custom algorithm was expected to perform well in test case types 1
JiraData are unique. That is, the solver can find a minimal solution and 2. However, this seems not be the case. Out of 150 test cases, the
with MinDomLBSearch and even prove its optimality. algorithm finds better solutions than the the ’normal’ minimizer in
8 This test was performed with a different, weaker computer than the nor- 18 cases. In the clear majority of cases, it performs worse.
mally used one.
Table 9. Maximization of sum of attribute 2 (e.g. utility). Results of 60 second timeout compared with 10 and 3 second timeouts. The custom algorithm is
excluded. Higher sum of attribute 2 (a2) is better. T est: the type of the testcases, #a: the number of attributes in the test cases. N60 : the average number of
features in a solution found with the 60s timeout. a160 , a260 :average value of attribute 1 / attribute 2 in solutions identified with 60s timeout, respectively.
N10,a2,< and N10,a2,= : the number of test cases where 10s timeout search finds a lower / same same sum of attribute 2 than the 60s version, respectively.
∆N10 (%) : the average difference (percentage) between number of included features between 60s and 10s timeout versions. ∆a210 (%): the average
difference (percentage) between sum of attribute 2 of included features between 60s and 10s timeout versions. 3 second timeouts are analogous, SynData2.
T est #a N60 a160 a260 N10,a2,< N10,a2,= ∆N10 (%) ∆a210 (%) N3,a2,< N3,a2,= ∆N3 (%) ∆a23 (%)
0 2 976 48979 49255 0 25 0.0% 0.0% 0 15 0.0% 0.0%
1 2 33.2 1000 1821 24 1 -2.1% -4.1% 15 0 -2.9% -5.9%
2 2 33.5 998 1831 21 4 -3.4% -4.6% 13 2 -5.7% -6.5%
3 2 53.6 1998 2860 23 2 -2.1% -3.2% 15 0 -3.6% -4.5%
Determining search strategy The best search strategy for our [3] Timo Asikainen, Tomi Männistö, and Timo Soininen, ‘Kumbang: A do-
purposes is bestBound(minDomLBSearch()) instead of plain main ontology for modelling variability in software product families’,
Advanced Engineering Informatics Journal, 21(1), (2007).
minDomLBSearch(), because it provides slighly better results in [4] D. Benavides, S. Segura, and A. Ruiz-Cortes, ‘Automated analysis of
minimization tests and maximizes significantly better. feature models 20 years later: A literature review’, Information Systems,
35(6), 615–636, (2010).
[5] David Benavides, Pablo Trinidad, and Antonio Ruiz-Cortes., ‘Auto-
6 CONCLUSIONS mated reasoning on feature models’, in 17th Conference on Advanced
Information Systems Engineering (CAiSE), (2005).
Solutions without optimization are easy to find; solvers such as [6] David Benavides, Pablo Trinidad, and Antonio Ruiz-Cortes, ‘Using
Choco have an easy task with sparse dependencies. Still, at least for constraint programming to reason on feature models’, in International
Conference on Software Engineering and Knowledge Engineering,
optimization, the selection of a search strategy matching the prob- (2005).
lem at hand remains crucial. It was surprising that the ”black-box” [7] Frédéric Boussemart, Fred Hemery, Christophe Lecoutre, and Lakhdar
activityBasedSearch[14] and Choco default domOverWDeg[7] did Sais, ‘Boosting systematic search by weighting constraints’, in Pro-
not perform in a satisfactory way. ceedings of the 16th European Conference on Artificial Intelligence,
The prototype engine easily scales to around 2000 requirements, pp. 146–150. IOS Press, (2004).
[8] K. Czarnecki, S. Helsen, and U. W. Eisenecker, ‘Formalizing
even when optimization is desired. Despite some remaining perfor- cardinality-based feature models and their specialization’, Software
mance issues, it seems that the approach can scale into managing the Process: Improvement and Practice, 10(1), 7–29, (2005).
requirements of large software projects, even for interactive use. [9] Maya Daneva and Andrea Herrmann, ‘Requirements prioritization
However, very large software projects, such as QT-BUG remain based on benefit and cost prediction: A method classification frame-
work’, in 34th Euromicro Conference on Software Engineering and Ad-
challenging. A more close examination of the Qt Jira is required, be- vanced Applications (SEAA), pp. 240–247, (2008).
cause it seems that performance can be managed in various ways. [10] Juan M. Carrillo de Gea, Joaqun Nicols, Jos L. Fernndez Alemn, Am-
First, there are different types of issues such as bugs and require- brosio Toval, Christof Ebert, and Aurora Vizcano, ‘Requirements en-
ments that do not need to be considered at the same time. Second, Qt gineering tools: Capabilities, survey and assessment’, Information and
has used Jira over a decade and there is a lot of historical data. The Software Technology, 54(10), 1142 – 1157, (2012).
[11] S. Gregor, ‘The nature of theory in information systems’, MIS Quar-
rate of new Jira issues seems to be up to 20 per a day. So, consider- terly, 30(3), 611–642, (2006).
ing only issues created or modified within three years would signifi- [12] K.C. Kang, S.G. Cohen, J.A. Hess, W.E. Novak, and A.S. Peterson,
cantly decrease the amount of data. Third, the exact nature of Qt data ‘Feature-oriented domain analysis (FODA) feasibility study’, Technical
and practical applications need to be inspected in more detail; now Report CMU/SEI-90-TR-21, Software Engineering Institute, (1990).
[13] D. Maplesden, E. Tempero, J. Hosking, and J. C. Grundy, ‘Performance
it seems that only about 10% of issues have dependencies, and the analysis for object-oriented software: A systematic mapping’, IEEE
compositional hierarchy such as epics decomposed to smaller items Transactions on Software Engineering, 41(7), 691–710, (July 2015).
needs a few levels at most. [14] Laurent Michel and Pascal Van Hentenryck, ‘Activity-based search
The concept of Dependency Engine is novel and it seems to be for black-box constraint programming solvers’, in International Con-
feasible for its intended use for providing holistic support for the ference on Integration of Artificial Intelligence (AI) and Operations
Research (OR) Techniques in Constraint Programming, pp. 228–243.
management of dependencies, also in the context of large software Springer, (2012).
projects. [15] Charles Prud’homme, Jean-Guillaume Fages, and Xavier Lorca, Choco
Documentation, TASC, INRIA Rennes, LINA CNRS UMR 6241,
COSLING S.A.S. www.choco-solver.org, 2016.
ACKNOWLEDGEMENTS [16] P-Y. Schobbens, P. Heymans, J-C. Trigaux, and Y. Bontemps, ‘Generic
semantics of feature diagrams’, Compututer Networks, 51(2), (2007).
This work has been funded by EU Horizon 2020 ICT-10-2016 grant [17] Mikael Svahnberg, Tony Gorschek, Robert Feldt, Richard Torkar,
No 732463. We thank the Qt Company for sharing the data. Saad Bin Saleem, and Muhammad Usman Shafique, ‘A systematic re-
view on strategic release planning models’, Information and Software
Technology, 52(3), 237 – 248, (2010).
[18] R. Thakurta, ‘Understanding requirement prioritization artifacts: a sys-
REFERENCES tematic mapping study’, Requirements Engineering, 22(4), 491–526,
(2017).
[1] Philip Achimugu, Ali Selamat, Roliana Ibrahim, and Mohd Nazri
[19] Juha Tiihonen, Mikko Raatikainen, Varvana Myllärniemi, and Tomi
Mahrin, ‘A systematic literature review of software requirements prior-
Männistö, ‘Carrying ideas from knowledge-based configuration to soft-
itization research’, Information and Software Technology, 56(6), 568–
ware product lines’, in International Conference on Software Reuse, pp.
585, (2014).
55–62, (2016).
[2] David Ameller, Carles Farré, Xavier Franch, and Guillem Rufian, ‘A
survey on software release planning models’, in Product-Focused Soft-
ware Process Improvement, (2016).