Search Based Software Engineering: Techniques, Taxonomy, Tutorial - Empirical Software Engineering and Verification - page 40

Table 5. Typification of the Next Release Problem under the Proposed Taxonomy

A. SOFTWARE ENGINEERING Perspective
1. Software Development Stage(s)
Requirement Engineering
2. Software Development Model(s)
Iterative and Incremental Development
Agile Development
3. Main Subject Descriptor(s)
D.2.1 Requirements/Specification
4. Main Implicit Subject Descriptor(s)

B. OPTIMISATION Perspective
1. Objective Space Dimensionality
Mono-objective
2. Instance Space Characterisation
Discrete
3. Constrained
Yes
4. Problem Linearity
Linear
5. Base NPO Problem Type(s)
MATHEMATICAL PROGRAMMING
6. Base NPO Problem(s)
MAXIMUM KNAPSACK

problem can be considered linear as well. Finally, it involves the solution of a
MATHEMATICAL PROGRAMMING problem, as defined in the “Compendium
of NP Optimisation Problems”. In fact, the Next Release Problem can be seen
as a specialisation of the MAXIMUM KNAPSACK Problem, as discussed next.
Consider the mathematical definition of the MAXIMUM KNAPSACK
problem, as presented in [22]:

MAXIMUM KNAPSACK

Z + and a value v ( u ) Z + ,

Instance: Finite set U ,foreach u ∈ U asize s ( u ) ∈ ∈

Z + .

a positive integer B ∈

U such that u∈U s ( u )

Solution: A subset U ⊆ B .

Measure: Total weight of the chosen elements, i.e., u∈U v ( u ).

≤

As defined in Instance ,theset U can represent the customers which may have
their requirements delivered in the next software release. Each customer, u ∈ U ,