Extended Feature models

Description

Feature models are used to denote software product lines. A software product line is a set of software products, and a software product is a set of features. An example of a feature model (from [1]) is:

·

The root feature (Mobile Phone) belongs to every product.

·

For every other feature than the root, it cannot be in a product without its parent. So, aproduct which contains MP3, also contains Media.

·

A mandatory feature belongs to the product if its parent does. So, Calls and Screen belong to every product.

·

An optional feature may or may not belong to a product. So, GPS and Media may or may not belong to a product.

·

From an alternative group, a product contains exactly one feature (provided the parent is in the product). So a product has either Basic, or Colour , or High resolution.

·

From an Or group, a product contains one or more features (provided the parent is in the product). So, If a product contains Media, it contains Camera, or it contains MP3, or it contains both Camera and MP3

·

Constraint of the form A requires B: If a product contains A then it contains B as well. So, If a product contains Camera, it contains High Resolution as well.

·

Constraint of the form A excludes B: a product may not contain A and B at the same time. So,there are no products with both GPS and Basic.

Analysis of feature models is usually done by using a Constraint Solvers, which are tools which solve Constraint Satisfaction Problems. Recently, it has been shown [2] that feature models can be analyzed using Integer Programming. In the case of extended feature models, analysis can be done with Constraint Solvers, or, when all constraints are linear, with Mixed Integer Programming.

List of Tasks

·

Study (the relevant parts of) [1]. Section 2.3 of this paper discusses extended feature models. Extended feature models are feature models whose features can have attributes, just like objects in OO programming can have attributes.

·

Study the literature on extended feature models, and compile a survey report. The literature encompasses:

(1)

The paper [1]

(2)

The papers referred to in section 2.3 of [1], especially [11].

(3)

The paper http://www.springerlink.com/content/26v8384w234uxuh1/

(4)

Any other literature that you can find.

·

Choose a number of examples of extended feature models with linear constraints.

·

Download a Constraint Solver and a Mixed Integer Programming tool, and execute the selected examples on both tools. Provide a detailed comparison of the two analysis methods.

References

[1] “Automated Analysis of Feature Models 20 Years Later: A Literature Review” by David Benavides, Sergio Segura and Antonio Ruiz-Cortes. It is available at http://www.lsi.us.es/~dbc/en/?Research.

[2] van den Broek, P.M. (2010) Optimization of Product Instantiation using Integer Programming. In: Proceedings of the 14th International Software Product Line Conference, Volume 2, 14 Sep 2010, Jeju Island, South Korea. pp. 107-111. Lancaster University, Lancaster, UK. ISBN 978-1-86220-274-0 http://eprints.eemcs.utwente.nl/18086/

Supervisor

Pim van den Broek