Dependency-aware release planning for software projects using fuzzy graphs and integer programming

Abstract

Software Release Planning (SRP) is to find, for a software, a subset of the requirements with the highest value while respecting the budget. The value of a requirement however may, to various degrees, depend on selecting or ignoring other requirements. However, existing SRP models ignore either Value-Related Dependencies altogether or the strengths of those dependencies even if they consider them. This paper presents an Integer Programming model for software release planning, which considers the variances of strengths of positive and negative value-related dependencies among software requirements. To capture the imprecision associated with strengths of value-related dependencies we have made use of algebraic structure of fuzzy graphs. We have further, contributed a scalable technique for automated identification of value-related dependencies based on user preferences for software requirements. The validity of the work is verified through simulations.

Keywords

Fuzzy Graphs Integer Programming Value-Related Dependencies Release Planning

1 Introduction

Owing to budget constraints, software release planning (SRP) [1, 2] is needed to find a subset of software requirements (optimal set) with the highest value while keeping the cost of the selected requirements within the available budget [3]. The value of a requirement however, may be positively or negatively influenced by selecting or ignoring other requirements due to the dependencies among values of requirements [4 –7]. Value-related dependencies [8, 9], also known as Increases-Decreases-value-of [7, 10], CVALUE [8], and Positive-Negative value dependencies [11] are commonly found in software projects [8 , 13]. Requirement dependencies, including value-related requirement dependencies, on the other hand, are fuzzy relations [8 , 15] meaning that the strengths of those dependencies are imprecise and vary from large to insignificant in the context of real software projects [6 , 17]. It is important thus, to consider not only the existence but also the strengths of value-related dependencies [5 , 18] in software release planning. Carlshamre et al. [8] observed the need to consider the strengths of requirement dependencies but they did not go further on how to formally achieve this. However, the existing software release planning models either ignore requirement dependencies [19 –21] or do not consider the variance of strengths of those dependencies [2 , 22] by treating them as precede relations [23, 24]. Following the latter direction, ignoring (selecting) a requirement r_i results in ignoring all of the requirements whose values positively (negatively) depend on r_i even if budget allows for their implementation [9].

This results in a condition referred to as the Selection Deficiency Problem (SDP) [25]. As a result of the SDP, any increase in the number of value-related dependencies will significantly reduce the value of the selected requirements [9].

To avoid these issues and properly factor value-related dependencies in software release planning, We proposed the notion of “Dependency-Aware Software Release Planning” in our earlier works [28, 29] to account for value-related dependencies. To achieve this, we have presented four major contributions as follows.

First, we have formulated an integer programming [26] model referred to as the Dependency-Aware Software Release Planning (DA-SRP) that finds a subset of software requirements with the highest Overall Value (OV), where overall value captures the influences of value-related dependencies (derived from user preferences) on the value of a selected subset of requirements. The DA-SRP model considers qualities (positivity or negativity) and strengths of value-related requirement dependencies.

Second, we have introduced Value Dependency Graphs (VDGs) based on fuzzy graphs [29, 30] for modeling value-related requirement dependencies and capturing the imprecision associated with strengths of those dependencies. A modified version of the Floyd-Warshall algorithm [31] is devised to infer implicit value-related dependencies in polynomial time.

Third, we have contributed a scalable technique for automated identification of explicit value-related dependencies and their characteristics (quality and strength) on the basis that values of software requirements are determined by user preferences for those requirements. In this regard, we have demonstrated using Eells measure of casual strength [32] for extracting qualities and strengths of value-related dependencies from user preferences. We have further, discussed value implications of certain structural and semantic dependencies among software requirements.

Finally, we have enhanced the accuracy of our proposed dependency identification technique through generating samples of large quantities based on the estimated distribution of the collected user preferences. In this regard, we have made use of a resampling [33] technique that generates samples from user preferences using a Latent Multivariate Gaussian model [33]. The employed resampling technique is computationally efficient and feasible for large numbers of software requirements [34].

We have verified the validity of the work by carrying out several simulations. Our results show that: (a) the DA-SRP model can properly consider qualities and strengths of value-related requirement dependencies in a SRP process while being computationally scalable, (b) The proposed DA-SRP model efficiently mitigates the adverse impact of the selection deficiency problem SDP, (c) the DA-SRP model always maximizes the overall value of the selected requirements, and (d) maximizing the overall value of a subset of requirements, where value-related dependencies are considered, and maximizing the Accumulated Value (AV) of that subset, where value-related dependencies are not considered, are conflicting objectives [35].

2 Related work

Several works [4 , 37] have focused the attentions on considering value-related dependencies in software release planning (SRP). On this basis, we categorize the existing software release planning models into there main groups as follows.

The first group [19 –21] of release planning models referred to as Binary Knapsack Problem (BKP) models find a subset of requirements with the highest accumulated value while ignoring value-related dependencies among requirements. Such models hence are formulated as the classical binary knapsack problem [23] as given by (1)-(3), where for a given set of requirements R : {r₁, . . . , r_n}, c_i and v_i denote the (estimated) cost and the (estimated) value of a requirement r_i ∈ R respectively. Also, b denotes the available budget and decision variable x_i specifies whether a requirement r_i is selected (x_i = 1) or not (x_i = 0).

$Maximize \sum_{i = 1}^{n} v_{i} x_{i}$ (1) $Subject to \sum_{i = 1}^{n} c_{i} x_{i} \leq b$ (2) $x_{i} \in {0, 1}, i = 1, . . ., n$ (3) The second group of software release planning models [2 , 37–39] referred to as Binary Knapsack with Precedence Constraint (BKP-PC) models, only capture value-related dependencies of full strength and formulate them as precedence constraints as given by (4)-(7). The rest of the value-related dependencies thus, have to be either ignored or treated as full-strength dependencies. Following the latter direction, a positive value-related dependency from a requirement r_j to r_k (Q (r_j, r_k) =+) is modeled as x_j ≤ x_k while a negative value-related dependency (Q (r_j, r_k) =-) is modeled as x_j ≤ 1 - x_k. Q (r_j, r_k) gives the quality of the dependency from r_j to r_k.

$Maximize \sum_{i = 1}^{n} v_{i} x_{i}$ (4) $Subject to \sum_{i = 1}^{n} c_{i} x_{i} \leq b$ (5) ${\begin{matrix} x_{j} \leq x_{k} & Q (r_{j}, r_{k}) = + \\ x_{j} \leq 1 - x_{k} & Q (r_{j}, r_{k}) = -, j \neq k = 1, . . ., n \end{matrix}$ (6) $x_{i} \in {0, 1}, i = 1, . . ., n$ (7)

Ignoring the strengths of value-related dependencies and molding them as precedence constraints however, results in a condition referred to as the selection deficiency problem (SDP) [25]. The reason is that when value-related dependencies are formulated as precedence constraints of (6), ignoring (selecting) a requirement r_i would result in ignoring all of the requirements whose values positively (negatively) depend on selection of r_i even if the available budget is enough to allow for their implementation [9]. Hence, employing BKP-PC models may result in loss of value due to the selection deficiency problem. The effect of the SDP is also demonstrated in a simulation study carried out by Li et al. [9] where a 2% increase in the number of requirement dependencies resulted in almost 10% loss of value in the optimal set.

To care for variances of value-related dependencies, the third group of release planning models [4 , 37] referred to as Increase-Decrease models consider value-related dependencies among software requirements through estimating the amount of the increased (decreased) values resulted by selecting various subsets of requirements.

An Increases-Decreases model proposed by Akker et al. [36] is given in (8)-(11). For a subset s_j ∈ S : {s₁, . . . , s_m} , m ≤ 2ⁿ, with n_j requirements, the difference between the estimated value of s_j (w_j) and the accumulated value of the requirements in s_j (∑_{r_k∈s_j}v_k) is considered when computing the value of the selected requirements. y_j in (8) specifies whether a subset s_j is realized (y_j = 1) or not (y_j = 0). Also, constraint (10) ensures that y_j = 1 only if ∀r_k ∈ s_j, x_k = 1.

$Maximize \sum_{i = 1}^{n} v_{i} x_{i} + \sum_{j = 1}^{m} (w_{j} - \sum_{r_{k} \in s_{j}} v_{k}) y_{j}$ (8) $Subject to n_{j} y_{j} \leq \sum_{r_{k} \in s_{j}} x_{k}$ (9) $\sum_{i = 1}^{n} c_{i} x_{i} \leq b$ (10) $x_{i}, y_{j} \in {0, 1} i, j = 1, . . ., n$ (11)

Increase-Decrease models however, are complex, subjective, and prone to human error as they rely on manual estimations for various subsets of requirements [25]. These problems persist even when estimations are limited to pairs of requirements [4 , 37] as given in (12)-(14). For n requirements, a pairwise approach would reduce the worst case complexity of manual estimations from estimating all subsets (O (2ⁿ)) to estimating the subsets of size two only (O (n²)) which is still way too complex to be used in software release planning.

$Maximize \sum_{i = 1}^{n} v_{i} x_{i} + \sum_{i = 1}^{n} \sum_{j = 1}^{n} w_{i, j} y_{i, j}$ (12) $Subject to \sum_{i = 1}^{n} c_{i} x_{i} \leq b$ (13) $x_{i}, y_{i, j} \in {0, 1} i, j = 1, . . ., n$ (14)

Furthermore, relying on pairwise estimations results in ignoring implicit value-related dependencies among software requirements as the direction of dependencies are not specified in estimated increased (decreased) values. For instance, consider requirements R : {r₁, r₂, r₃}, where the value of r₁ positively depends on r₂ and the value of r₂ positively depends on r₃. On this basis, it is logical to infer an implicit positive value-related dependency from r₁ to r₃. An Increase-Decrease model however, fails to capture this implicit dependency even if pairwise estimations show that selecting r₁ and r₂ as a pair, increases the value of that pair and the estimated value of the requirements r₂ and r₃ increases when selected together. As such, if no explicit value-related dependency is identified between r₁ and r₃ by pairwise estimations, the influence of r₃ on the value of r₁ will be ignored by the Increase-Decrease model.

3 Modeling Value-related dependencies by Fuzzy Graphs

It is widely known that using graphs for modeling requirement dependencies [8 , 40–42] results in enhancing the accuracy of release planning [8]. On the other hand, fuzzy graphs and their algebraic structure have demonstrated to contribute to more accurate models as they can properly capture the imprecision associated with requirement dependencies [16, 17].

On this basis, we have introduced Value Dependency Graphs (VDGs) based on the classical fuzzy graphs for modeling value-related dependencies and their characteristics (quality and strength) in software projects. We have specially modified the classical definition of fuzzy graphs to consider not only the strength but also the quality of value-related dependencies as given by Definition 3.

Definition 1. Value Dependency Graph (VDG). A VDG is a signed directed fuzzy graph [43] G = (R, σ, ρ) in which a non-empty set of identified requirements R : {r₁, . . . , r_n} constitute the graph nodes. The qualitative function σ : R × R → {+ , - , ±} and the membership function ρ : R × R → [0, 1] denote qualities (positivity and negativity) and strengths of explicit value-related dependencies (edges of the graph) receptively. As such, a pair of requirements (r_i, r_j) with ρ (r_i, r_j) ≠0 denotes a positive (negative) value-related dependency from r_i to r_j stating that selection of r_j has an explicit positive (negative) influence on the value of r_i which is equivalent to r_j is a positive (negative) value-related dependence of r_i.

For instance, in the VDG G = (R, σ, ρ) of Figure 1 with R = {r₁, r₂, r₃, r₄, r₅}, σ (r₁, r₂) =+ and ρ (r₁, r₂) =0.4 state that selection of requirement r₂ has an explicit positive influence on the value of requirement r₁ and the strength of this influence is roughly 0.4. It is clear that we have ρ (r_i, r_j) =0 if the value of a requirement r_i is not explicitly influenced by selection of r_j. In such cases we have σ (r_i, r_j) =±, where ± denotes the quality of (r_i, r_j) is non-specified.

Fig. 1

A sample value dependency graph.

Definition 2. Value-Related Dependencies. A value-related dependency in a VDG G = (R, σ, ρ) is defined as a sequence of requirements d_i : (r (0) , . . . , r (k)) such that ∀r (j) ∈ d_i, 1 ≤ j ≤ k we have ρ (r (j - 1) , r (j)) ≠0. j ≥ 0 is the sequence of the j^th requirement (node) denoted as r (j) on the dependency path. A consecutive pair (r (j - 1) , r (j)) specifies an explicit value-related dependency.

The strength of a value-related dependency d_i : (r (0) , . . . , r (k)) is calculated by (15). That is, the strength of a value-related dependency equals to the strength of the weakest of all the k explicit value-related dependencies along the path. Fuzzy operator ∧ denotes Zadeh’s [44] fuzzy AND operation (taking infimum).

$\forall d_{i} : (r (0), . . ., r (k)) : ρ (d_{i}) =$ (15) $⋀_{j = 1}^{k} ρ (r (j - 1), r (j))$

$\forall d_{i} : (r (0), . . ., r (k)) : σ (d_{i}) =$ (16) $\prod_{j = 1}^{k} σ (r (j - 1), r (j))$

On the other hand, the quality (positive/negative) of a value-related dependency d_i : (r (0) , . . . , r (k)) is calculated through qualitative serial inference [45 –47] as given by (16) and Table 1. For instance, given d_i : (r (0) , r (1) , r (2)), we can infer from σ (r (0) , r (1)) =+ and σ (r (1) , r (2)) =- that σ (r (0) , r (1) , r (2)) =-. This can be informally proved as given in (17), where ¬r (2) denotes ignoring r (2).

Table 1

Qualitative Serial Inference in VDGs

σ (r (j - 1) , r (j) , r (j + 1))		σ (r (j) , r (j + 1))
		+	-	±
σ (r (j - 1) , r (j))	+	+	-	±
	-	-	+	±
	±	±	±	±

$(a) : σ (r (0), r (1)) = +$ (17) $\begin{matrix} (b) : σ (r (1), r (2)) = - \to σ (r (1), \neg r (2)) = + \\ (a), (b) \Rightarrow σ (r (0), r (1), \neg r (2)) = + \\ \to σ (r (0), r (1), r (2)) = - \end{matrix}$

Quantitative serial inferences in Table 1 are mathematically proved by Wellman [46] and Kleer [45]. Also, Kusiak [47] has explained the details of employing them in constraint negotiation.

Let D = {d₁, d₂, . . . , d_m} be the set of all explicit and implicit value-related dependencies from r_i ∈ R to r_j ∈ R in a VDG G = (R, σ, ρ). As explained earlier, positive and negative value-related dependencies can simultaneously exist from r_i to r_j. The strength of all positive value-related dependencies from r_i to r_j is denoted by ρ^+∞ (r_i, r_j) and calculated by (18), that is to find the strength of the strongest positive value-related dependency [30] among all the positive value-related dependencies from r_i to r_j. Fuzzy operators ∧ and ∨ denote Zadeh’s [44] fuzzy AND (taking minimum over AND-ed operands) and fuzzy OR (taking maximum over OR-ed operands) operations respectively. In a similar way, the strength of all negative value-related dependencies from r_i to r_j is denoted by ρ^-∞ (r_i, r_j) and calculated by (19).

$ρ^{+ \infty} (r_{i}, r_{j}) = ⋁_{d_{m} \in D, σ (d_{m}) = +} ρ (d_{m})$ (18) $ρ^{- \infty} (r_{i}, r_{j}) = ⋁_{d_{m} \in D, σ (d_{i}) = -} ρ (d_{m})$ (19)

A brute-force approach to calculating ρ^+∞ (r_i, r_j) or ρ^-∞ (r_i, r_j) would compute the strengths of all possible paths from r_i to r_j which could get as complex as O (n !), where n denotes the number of requirements (VDG nodes). To avoid such complexity, we have formulated the problem of calculating ρ^+∞ (r_i, r_j) and ρ^-∞ (r_i, r_j) as a widest path problem (also known as the maximum capacity path problem [48]) which can be solved in polynomial time by Floyd-Warshall [31] algorithm.

In this regard, we devised a modified version of Floyd-Warshall algorithm (Algorithm 1) that computes ρ^+∞ (r_i, r_j) and ρ^-∞ (r_i, r_j) for all pairs of requirements: ∀ (r_i, r_j) , r_i, r_j ∈ R : {r₁, . . . , r_n} with the time bound of O (n³). For each pair of requirements (r_i, r_j) in a VDG G = (R, σ, ρ), lines 20 to 36 of Algorithm 1 find the strength of all positive value-related dependencies and the strength of all negative value-related dependencies from r_i to r_j.

Algorithm 1 Calculating Strengths of Value Dependencies.

Input: VDG G = (R, σ, ρ)

Output: ρ^+∞, ρ^-∞

1: for each r_i ∈ R do

2: for each r_j ∈ R do

3: ρ^+∞ (r_i, r_j)← ρ^-∞ (r_i, r_j) ← - ∞

4: end for

5: end for

6: for each r_i ∈ R do

7: ρ (r_i, r_i) ^+∞ρ (r_i, r_i) ^-∞ ← 0

8: end for

9: for each r_i ∈ R do

10: for each r_j ∈ R do

11: if σ (r_i, r_j) =+ then

12: ρ^+∞ (r_i, r_j) ← ρ (r_i, r_j)

13: else if σ (r_i, r_j) =- then

14: ρ^-∞ (r_i, r_j) ← ρ (r_i, r_j)

15: end if

16: end for

17: end for

18: for each r_k ∈ R do

19: for each r_i ∈ R do

20: for each r_j ∈ R do

21: if min (ρ (r_i, r_k) ^+∞, ρ (r_k, r_j) ^+∞) >

ρ^+∞ (r_i, r_j) then

22: ρ^+∞ (r_i, r_j) ←

min (ρ (r_i, r_k) ^+∞, ρ (r_k, r_j) ^+∞)

23: end if

24: if min (ρ (r_i, r_k) ^-∞, ρ (r_k, r_j) ^-∞) >

ρ^+∞ (r_i, r_j) then

25: ρ^+∞ (r_i, r_j) ←

min (ρ (r_i, r_k) ^-∞, ρ (r_k, r_j) ^-∞)

26: end if

27: if min (ρ (r_i, r_k) ^+∞, ρ (r_k, r_j) ^-∞) >

ρ^-∞ (r_i, r_j) then

28: ρ^-∞ (r_i, r_j) ←

min (ρ (r_i, r_k) ^+∞, ρ (r_k, r_j) ^-∞)

29: end if

30: if min (ρ (r_i, r_k) ^-∞, ρ (r_k, r_j) ^+∞) >

ρ^-∞ (r_i, r_j) then

31: ρ^-∞ (r_i, r_j) ←

min (ρ (r_i, r_k) ^-∞, ρ (r_k, r_j) ^+∞)

32: end if

33: end for

34: end for

35: end for

The overall strength of all positive and negative value-related dependencies from r_i to r_j is referred to as the Overall Influence of r_j on the value of r_i and denoted by I_i,j. I_i,j as given by (20) is calculated by subtracting the strength of all negative value-related dependencies from r_i to r_j (ρ (r_i, r_j) ^-∞) from the strength of all positive value-related dependencies from r_i to r_j (ρ (r_i, r_j) ⁺∞). It is clear that I_i,j ∈ [-1, 1]. I_i,j > 0 states that r_j influences the value of r_i in a positive way whereas I_i,j < 0 indicates that the ultimate influence of r_j on r_i is negative.

$I_{i, j} = ρ^{+ \infty} (r_{i}, r_{j}) - ρ^{- \infty} (r_{i}, r_{j})$ (20)

Example 1. Consider the set of all value-related dependencies from requirement r₁ to requierment r₄: D = {d₁ = (r₁, r₂, r₄) , d₂ = (r₁, r₃, r₄) , d₃ = (r₁, r₄)} in the VDG of Figure 1. Using (16) qualities of value-related dependencies in D are calculated as follows. σ (d₁) = Π (+ , +) = +, σ (d₂) = Π (+ , +) = +, and σ (d₃) = Π (-) =-. Also strengths of value-related dependencies in D are calculated by (15) as: ρ (d₁) = ∧ (ρ (r₁, r₂) , ρ (r₂, r₄)) = min (0.4, 0.3) =0.3, ρ (d₂) = ∧ (ρ (r₁, r₃) , ρ (r₃, r₄)) = min (0.8, 0.8) =0.8, ρ (d₃) =0.1. Using (18) we have: ρ (r₁, r₄) ⁺ ∞ = ∨ (ρ (d₁) , ρ (d₂)) = max (0.3, 0.8) =0.8. Also using (19) we have ρ^-∞ (r₁, r₄) = ρ (d₃) =0.1. Therefore, we have I_1,4 = ρ (r₁, r₄) ^+∞ - ρ (r₁, r₄) ^-∞ = 0.7. I_1,4 = 0.7 > 0 indicates that positive influence of r₄ on the value of r₁ prevails. Table 2 lists overall influences of requirements of VDG of Figure 1 on the values of each other.

Table 2

Overall influences for VDG of Figure 1

I_i,j = ρ (r_i, r_j) ^+∞ - ρ (r_i, r_j) ^-∞	r ₁	r ₂	r ₃	r ₄
r ₁	0.0 - 0.0 = 0.0	0.6 - 0.1 = 0.5	0.8 - 0.1 = 0.7	0.8 - 0.1 = 0.7
r ₂	0.2 - 0.0 = 0.2	0.0 - 0.0 = 0.0	0.2 - 0.0 = 0.2	0.3 - 0.0 = 0.3
r ₃	0.7 - 0.1 = 0.6	0.6 - 0.1 = 0.5	0.0 - 0.0 = 0.0	0.8 - 0.1 = 0.7
r ₄	0.2 - 0.0 = 0.2	0.2 - 0.0 = 0.2	0.2 - 0.0 = 0.2	0.0 - 0.0 = 0.0

Definition 3. Value Dependency Level (VDL) and Negative Value Dependency Level (NVDL). Let G = (R, σ, ρ) be a VDG with R = {r₁, . . . , r_n}, k be the total number of explicit value-related dependencies in G, and m be the total number of negative explicit value-related dependencies. Then, VDL and NVDL of G are derived by (21) and (22) respectively. $VDL (G) = \frac{k}{^{n} P^{2}} = \frac{k}{n (n - 1)}$ (21) $NVDL (G) = \frac{m}{k}$ (22)

Example 2. Consider the value-related dependency graph G of Figure 1 for which we have n = 4, k = 8, and m = 1. VDL (G) is derived by (21) as: $VDL (G) = \frac{8}{4 \times 3} = \frac{8}{12} ≊ 0.67$ . Also we have from Equation (22), $NVDL (G) = \frac{1}{8} = 0.125$ .

4 Identifying explicit value-related dependencies

It has been widely known that the value of a software requirement is determined by user preferences (satisfaction) of that requirement. Hence, terms like customer value or business value have been preferred by some of the existing works [49, 50] to emphasize the importance of user (customer) preferences in specifying values of software requirements. User preferences for a software requirement however, may be influenced by user preferences for other requirements. In other words, users preferring (selecting or using) a requirement r_j maybe be more likely or less likely to prefer a requirement r_i. As such, the (customer) value of a software requirement can be influenced by user preferences for other requirements. Based on this logic, value-related dependencies among software requirements can be inferred from causal relations [32 , 51–54] among user preferences for those requirements. For instance, when user preferences for a requirement r_j positively influences user preferences for a requirement r_i, this implies a value-related dependency from r_i to r_j with ρ (r_i, r_j) ≠0 and σ (r_i, r_j) >0.

User preferences can be gathered in different ways [50 , 55–57] depending on the nature of a software release. For the very first release of a software, user preferences can be gathered by conventional market research approaches such as conducting surveys or referring to the user feedbacks or sales records of the similar software products in the market. For future releases of a software, or when re-engineering of a software is of interest (e.g. for legacy systems) however, user feedbacks and sales records of the previous releases of a software might be used in combination with market research results to find user preferences. Once user preferences are gathered, we can identify explicit value-related dependencies and their characteristics (namely quality and strength) using measures of causal strength [32 , 51–54].

In this paper, we have used one of the most widely adopted measures of causal strength referred ton as the Eells measure [32]. Eells measure for an explicit value-related dependency (r_i, r_j) is denoted by η_i,j and computed by (23). η_i,j specifies the extent to which selecting or ignoring r_j influences user preferences of r_i and consequently the value of r_i. Eells measure properly captures both positive and negative value-related dependencies between a pair of requirements through subtracting the conditional probability p (r_i| ¬ r_j) from p (r_i|r_j), where conditional probabilities p (r_i| ¬ r_j) and p (r_i|r_j) denote strengths of positive and negative dependencies from r_i to r_j respectively. ¬r_j denotes ignoring r_j.

$η_{i, j} = p (r_{i} | r_{j}) - p (r_{i} | \neg r_{j}), η_{i, j} \in [- 1, 1]$ (23)

Complexity of computing Eells measure for all pairs of requirements in a requirement set of size n is n² × u, where u is the number of users whose preferences are gathered. As such, the process is scalable to large number of requirements. Hence, automated identification of value-related dependencies adds a negligible overhead to software release planning.

$σ (r_{i}, r_{j}) = {\begin{matrix} + & if η_{i, j} > 0 \\ - & if η_{i, j} < 0 \\ \pm & if η_{i, j} = 0 \end{matrix}$ (24)

To identify quality of a value-related dependency (r_i, r_j), (24) gives a mapping from η_i,j to the qualitative function σ : R × R → {+ , - , ±}, where η_i,j > 0 indicates that the strength of the positive dependency from r_i to r_j is greater than the strength of its corresponding negative dependency: p (r_i|r_j) > p (r_i| ¬ r_j) and therefore the quality of d is positive (σ (r_i, r_j) =+). Similarly, η_i,j < 0 indicates p (r_i| ¬ r_j) > p (r_i|r_j) which means σ (r_i, r_j) =-. Also, p (r_i|r_j) - p (r_i| ¬ r_j) =0 specifies that the quality of the zero-strength value-related dependency (r_i, r_j) is non-specified (σ (r_i, r_j) =±).

To compute the strength of a value-related dependency (r_i, r_j) in a VDG G = (R, σ, ρ), (25) gives a mapping from η_i,j to the fuzzy membership function ρ : R × R → [0, 1]. This mapping is demonstrated in Figure 2(a). Nevertheless, other membership functions such as the one in Figure 2(b) could also be used for this mapping depending on the desired behavior of the release planning model used. For instance, the membership function of Figure 2(a) ignores value-related dependencies with casual strengths below 0.16 (η_i,j < 0.16) while dependencies with η_i,j ≥ 0.83 are considered strong enough to be formulated as full strength dependencies (ρ (r_i, r_j) =1).

Fig. 2

Sample membership functions ρ (r_i, r_j).

$ρ (r_{i}, r_{j}) = | η_{i, j} |$ (25)

When the number of user preferences gathered is limited, resampling can be used to generate samples of large (enough) quantities based on the estimated distribution of the collected user preferences. To achieve this, we use a scalable technique proposed by Macke et al. [34] to generate larger samples of user preferences using a Latent Multivariate Gaussian model [33]. Our resampling process starts with computing estimated means and variances of user preferences for each requirement. Then, covariances matrix of the requirements will be computed for generating new samples. Finally, samples of desired size will be generated based on the Dichotomized Gaussian Distribution model discussed in [33].

Finally, it is worth mentioning that, Intrinsic (structural or semantic) dependencies of full strength among software requirements (e.g. requires [7] and conflicts with [58]) also have value implications. For instance, a requirement r_i requires (conflicts with) r_j means that r_i can not give any value if r_j is ignored (selected). Hence, it is also important to be aware of value implications of intrinsic dependencies and consider them in software release planning. This could be achieved by carefully studying the structure (semantic) of a software.

5 The integer programming model

As explained earlier, the value of a software requirement is determined by user preferences for that requirement [10 , 59]. In other words, the higher the ratio of the users that prefer (select or use) a software requirement r_i, the higher the expected value of r_i would be. That means r_i can achieve its highest expected value (which equals to its estimated value) when all users of r_i are satisfied with that requirement. However, this only happens when user preferences for the requirement r_i is not negatively influenced by selecting or ignoring other requirements. In other cases, a reduction from the estimated value of r_i is predictable. The extent of such reduction is referred to as the penalty [60] of r_i and denoted as p_i.

$\begin{matrix} p_{i} = ⋁_{j = 1}^{n} \\ (\frac{x_{j} (| I_{i, j} | - I_{i, j}) + (1 - x_{j}) (| I_{i, j} | + I_{i, j})}{2}) = \\ ⋁_{j = 1}^{n} (\frac{| I_{i, j} | + (1 - 2 x_{j}) I_{i, j}}{2}), i = 1, . . ., n \end{matrix}$ (26) $x_{j} \in {0, 1}, j = 1, . . ., n$ (27)

We have made use of the algebraic structure of fuzzy graphs for modeling value-related dependencies and their characteristics (quality and strength) as explained in Section 3. Hence, p_i is calculated using fuzzy OR operator, which is to take supremum over the strengths of all ignored positive dependencies and selected negative dependencies of r_i in its corresponding value dependency graph. This is given in (26) and (33), where n denotes the number of requirements and x_j specifies whether a requirement r_j is selected (x_j = 1) or not (x_j = 0). Also, I_i,j denotes the overall strength of all positive and negative value-related dependencies from r_i to r_j which is referred to as the overall influence of r_j on the value of r_i as given in (20).

Equation (29) derives the expected value of a software requirement r_i denoted by $v_{i}^{'}$ which captures the impact of user preferences for r_i (φ_i) on the value of r_i. φ_i is derived by subtracting the penalty p_i from the ideal user preference (satisfaction) level 1 (when every user selects or uses r_i). As such, the overall value (OV) of a selected subset of requirements can be calculated by accumulating the expected values of the selected requirements as given by (30), where x_i denotes whether r_i is selected (x_i = 1) or not (x_i = 0).

$φ_{i} = 1 - p_{i}$ (28) $v_{i}^{'} = φ_{i} v_{i}$ (29) $OV = \sum_{i = 1}^{n} x_{i} (1 - p_{i}) v_{i}, x_{i} \in {0, 1}$ (30)

Example 3.For a candidate set s₁ = {r₁, r₂, r₃} (x₁ = x₂ = x₃ = 1, x₄ = 0) in VDG of Figure 1 consider finding penalties of selected requirements. From Table 2 we have I_1,4 = I_3,4 = 0.7, I_2,4 = 0.3, I_4,4 = 0.0. As such, based on (26) penalties can be calculated as $p_{1} = \lor (\frac{| 0.0 | + (1 - 2 (1)) (0.0)}{2}$ , $\frac{| 0.45 | + (1 - 2 (1)) (0.5)}{2}$ , $\frac{| 0.7 | + (1 - 2 (1)) (0.7)}{2}$ , $\frac{| 0.7 | + (1 - 2 (0)) (0.7)}{2}) = 0.7$ . In a similar way, we have p₂ = 0.3, p₃ = 0.7. By using (28) we have φ₁ = 1 -0.7 = 0.3, φ₂ = 1 -0.3 = 0.7, φ₃ = 1 -0.7 = 0.3. Therefore, achieved expected values of selected requirements r₁, r₂, r₃ can be derived by (29) as: $v_{1}^{'} = 0.3 (20) = 6, v_{2}^{'} = 0.7 (10) = 7, v_{3}^{'} = 0.3 (50) = 15$ . Hence, we have $OV (s_{1}) = \sum_{i = 1}^{4} x_{i} v_{i}^{'} = 28$ .

Our proposed release planning model referred to as the DA-SRP (Dependency-Aware Software Release Planning), maximizes the overall value (OV) of a selected subset of requirements considering value-related dependencies among requirements. Equations (31)-(35) give the integer programming model for DA-SRP, where x_i is a selection variable denoting whether a requirements r_i is selected (x_i = 1) or ignored (x_i = 0). Also, p_i specifies the penalty of a requirement r_i which is the extent to which ignoring positive value-related dependencies and selecting negative value-related dependencies of r_i reduce its expected value.

$Maximize \sum_{i = 1}^{n} x_{i} (1 - p_{i}) v_{i}$ (31) $Subject to \sum_{i = 1}^{n} c_{i} x_{i} \leq b$ (32) $p_{i} \geq (\frac{| I_{i, j} | + (1 - 2 x_{j}) I_{i, j}}{2}), i \neq j = 1, . . ., n$ (33) $x_{i} \in {0, 1} i = 1, . . ., n$ (34) $0 \leq p_{i} \leq 1 i = 1, . . ., n$ (35)

6 Simulations

6.1 Simulation design

Simulation of requirement dependencies has been proposed in several works from the literature [9 , 61] for analyzing the efficiency of release planning models. On this basis, we carried out simulations to compare efficiency of the DA-SRP model against that of the existing release planning models (BKP and BKP-PC models). The Increase-Decrease models however, could not be simulated as they do not specify how to formally achieve the amount of the increased or decreased values as explained in Section 2.

We simulated value-related dependencies among requirements of a real-world software project (Table 3) through random generation of qualities and strengths of explicit value-related dependencies. In doing so, for each candidate explicit value-related dependency (r_i, r_j), a random number with uniform distribution in [-1, 1] was generated whose sign and magnitude determined the quality and the strength of (r_i, r_j) respectively. A randomly generated 0 was interpreted as the absence of any explicit value-related dependency from r_i to r_j. Experiments were repeated for various levels of value-related dependencies (VDLs) and negative value-related dependencies (NVDLs) among requirements. To achieve this, certain VDLs and NVDLs were imposed on the value-related dependency graph the requirements by randomly removing edges (explicit value-related dependencies) of the graph. Also, experiments were repeated for different percentages of budgets %Budget ∈ [0, 100] to investigate efficiency of the experimented release planning models in the presence of various budget constraints.

Table 3
Estimated costs and values of the requirements

Requirement r ₁ r ₂ r ₃ r ₄ r ₅ r ₆ r ₇ r ₈ r ₉ r ₁₀ r ₁₁ r ₁₂ r ₁₃ r ₁₄ r ₁₅ r ₁₆ r ₁₇ r ₁₈ r ₁₉ r ₂₀ r ₂₁ r ₂₂ r ₂₃ r ₂₄ r ₂₅ r ₂₆ r ₂₇ Sum

Cost 5.0 20.0 0.0 10.0 1.0 20.0 6.0 5.0 16.0 10.0 4.0 3.0 5.0 7.0 15.0 13.0 14.0 3.0 10.0 7.0 12.0 15.0 8.0 2.0 10.0 0.0 1.0 222.0

Value 10.0 20.0 4.0 17.0 3.0 20.0 15.0 9.0 20.0 16.0 20.0 10.0 6.0 8.0 8.0 10.0 6.0 10.0 20.0 20.0 15.0 20.0 20.0 5.0 0.0 0.0 0.0 312.0

6.2 Simulation results and discussion

Figure 3 and Figure 4 show percentages of the overall value (%OV = (OV/312) ×100) and percentages of the accumulated value (%AV = (AV/312) ×100) achieved from the experimented software release planning (SRP) models for two different levels of negative value-related dependencies (NVDL = {0.0, 0.5}). Give a NVDL, the experiments were repeated for various value dependency levels (VDL ∈ {0, 0.001, . . . , 1}), and different percentages of budget (%Budget = (Budget/222) ×100) as denoted by x-axis and y-axis respectively (Figure 3 and Figure 4). For selected subsets of requirements the color-bars in Figure 3 and Figure 4 denote the %OV and the %AV respectively. All our simulation results consistent with the results of our case study showed (Figure 3 and Figure 4) that for all %Budget, VDLs, and NVDLs, the BKP model always found a subset of requirements with the highest (compared to the BKP-PC and DA-SRP models) accumulated values while overall values of those subsets were not necessarily the highest. The DA-SRP model on the other hand, always found subsets of requirements with the highest overall values while accumulated values of those subsets were not necessarily the highest.

It was thus, concluded that maximizing the accumulated value of an optimal set and maximizing the overall value of that set are conflicting objectives. Nonetheless, for a given %Budget, the %OV and the %AV provided by the BKP and DA-SRP models tended to reduce and converge as NVDL was increased. To formally explain this, more information is needed. However, we can informally state that by increasing the NVDL, the chances that a selected requirement negatively influences the values of other selected requirements, will increase. As such, the chances will increase that ignoring a requirement r₁ reduces the value of a requirement r₂ (already selected) while selecting r₁ reduces the value of a third requirement r₃. The impact of increasing NVDL can be clearly observed in Figures 3(d), 3(e), 3(f), where %OV = 100 has almost never been achieved even in the presence of a sufficient budget. This is more significant in the case of the BKP-PC model (Figure 3(f)). The reason is that due to the selection deficiency problem (SDP) in BKP-PC models, increasing negative value-related dependencies will increase the chances that either selecting or ignoring requirements violates the precedence constraints and turn the candidate subset of requirements to an infeasible solution.

Fig. 3

Overall values achieved from simulated software release planning models.

We also observed (Figure 3 and Figure 4) in all experiments that overall values given by BKP-PC model were equal to their corresponding accumulated values. The reason is that the BKP-PC model treats all value-related dependencies as binary relations which results in a situation, where a requirement is only selected if all of its positive (negative) value-related dependencies are selected (ignored). As such the penalties of requirements are always calculated as 0.

Our results further, showed the selection deficiency problem (SDP) [25] severely impacted the %AV and %OV achieved from the BKP-PC model in general. This was further exacerbated for higher NVDLs as in such cases not only ignoring but selecting certain requirement resulted in value loss due to the presence of negative value-related dependencies. For instance, for NVDL = 0.0 we have VDL > 0.12, % Budget < 100 ⇒ % AV (BKP - PC) = % OV (BKP - PC) =0 while for NVDL = 0.5 we have VDL > 0.07 ⇒ % AV (BKP - PC) = % OV (BKP - PC) =0.

Finally, we observed (Figure 3 and Figure 4 that) that DA-SRP properly mitigated the impact of SDP by providing some %AV and %OV when the BKP-PC model was not able to provide any value. The reason is DA-SRP considers the impacts of the ignored (selected) positive (negative) value-related dependencies rather than treating those dependencies as binary (exists/does not exist) relations. The BKP model however is not subject to the SDP as it completely ignores requirement dependencies all types.

Fig. 4

Accumulated values achieved from simulated software release planning models.

7 Scalability

Scalability of the work has two main aspects. First, scalability of the dependency identification and second, scalability of our proposed selection model (DA-SRP). Regarding the scalability of the dependency identification, we have automated the process of identifying value-related dependencies based on user preferences for software requirements as described in Section 4. Hence, there would be no need for manual comparisons. Our automated dependency identification process is based on the fact that the (expected) value of a requirement is determined by user preferences for that requirement. In this regard, Eells measure of casual strength [32] is used to measure strengths of value-related dependencies based on user preferences.

The algorithm for computing Eells measure is computationally efficient as it only calculates conditional probabilities for pairs of requirements and their complements. For n requirements hence the complexity is of O (n²). We have further suggested considering value-implications of precede dependencies (r₁ requires/precedes/conflicts-with r₂) when such information is available. Precede dependencies are normally identified prior to the release planning as part of requirement analysis. Identifying such dependencies is not specific to our release planning model and therefor does not add any additional overhead to it.

DA-SRP, as given by (31)-(35), formulates a Convex Optimization Problem since the model maximizes a Concave objective function over linear constraints [62]. Convex optimization problems are known to be efficiently solvable [62]. To further improve this we used the technique introduced in [63] to linearize the DA-SRP model. The model showed to be scalable to large number of requirements as depicted in simulations results of Figure 5). We performed simulations to demonstrate scalability of the DA-SRP model in comparison with the existing BKP and BKP-PC models. Uniformly distributed random numbers were generated to simulate the costs and values of requirements as well as the strengths of value-related dependencies among them. The callable library ILOG CPLEX [64] was used to implement and run the BKP, BKP-PC, and the DA-SRP models. All simulations were performed on a Windows machine (Windows 8.1) with 8 GB of RAM and a Core i5-4300 CPU with the speed of 1.9 GHz to 2.49 GHz.

Fig. 5

Runtime of experimented SRP models for different numbers of requirements (size).

Figure 5 shows our results with a logarithmic y-axis specifying the run-time of the experimented release planning models and a linear x-axis denoting the size of the experiment (the total number of requirements). Our simulations for random requirement sets of various sizes (Size = {0, 1, . . . , 2000}) demonstrated (Figure 5) that the DA-SRP model always found the optimal subset of the requirements (a subset with the highest overall value for a given budget) in less than 2 minutes. However, the run-time of the DA-SRP model was higher than that of the BKP and BKP-PC models while the BKP model performed faster than the BKP-PC and DA-SRP models (Figure 5). The reason is the BKP model ignores value-related dependencies and therefore can be executed in semi-polynomial time using dynamic-programming [65] while the BKP-PC needs to satisfy the precedence constraints which capture value-related dependencies and therefore, it takes longer for the BKP-PC model to find the optimal subset of the requirements (solution). The DA-SRP model on the other hand, considers value-related dependencies in addition to the precedence constraints, which increases the execution time of the model and makes it slower than BKP and BKP-PC in general.

8 Conclusions and future work

In this paper we presented an integer programming model for software release planning which optimizes the overall value of a software release by considering strengths and qualities of value-related dependencies among software requirements. We further introduced, based on fuzzy graphs, value dependency graphs and their algebraic structure for modeling value-related dependencies and reasoning about qualities and strengths of those dependencies. A modified version of the Floyd-Warshall algorithm was introduced to infer value-related dependencies and their characteristics in polynomial time. Moreover, a scalable technique was proposed for automated identification of explicit value-related dependencies and their characteristics based on user preferences. We also demonstrated application of a latent multivariate Gaussian model for generating samples of large (enough) quantities from user preferences to enhance accuracy of dependency identification.

We demonstrated through studying an industrial software project and conducting several simulations that: (a) the DA-SRP model can properly capture value-related dependencies in software release planning while being reasonably scalable, (b) the proposed DA-SRP model efficiently mitigates the selection deficiency problem, (c) the DA-SRP model always maximizes the overall value of selected requirements, and (d) maximizing the overall value, with considering value-related dependencies, and the accumulated value, without considering value-related dependencies, of a selected subset of software requirements are conflicting objectives.

This work can be extended in several directions. One is to explore different measures of casual strength and comparing their efficiency in capturing value-related dependencies. To assist dependency identification, one may also consider mining online resources such as social media and software repositories. In this paper we studied value as the economic worth of a software. But, it is also important to consider social aspects of software and their impacts on the society. Considering social values of software are particularly important to stakeholders with special preferences e.g. users with disabilities. It would be interesting hence to integrate social values in software through considering those values in software release planning. In this regard, considering dependencies/conflicts among social values and reconciling those into software would be imperative.

References

Franch

and Ruhe

, Software release planning, in: Proceedings of the 38th International Conference on Software Engineering Companion, ACM, 2016, pp. 894–895.

Bagnall

A.J.

, RaywardSmith

V.J.

and Whittley

I.M.

, The next release problem, Information and Software Technology 43(14) (2001), 883–890.

Dahlstedt

A.G.

and Persson

, Requirements interdependencies - moulding the state of research into a research agenda, Ninth International Workshop on Requirements Engineering: Foundation for Software Quality (REFSQ 2003), 2003, 71–80.

Zhang

, Harman

and Lim

S.L.

, Empirical evaluation of search based requirements interaction management, Information and Software Technology 55(1) (2013), 126–152, special section: Best papers from the 2nd International Symposium on Search Based Software Engineering 2010.

Brasil

M.M.A.

, d Silva

T.G.N.

, d Freitas

F.G.

, d Souza

J.T.

and CortÃl’s

M.I.

, A multiobjective optimization approach to the software release planning with undefined number of releases and interdependent requirements, in: Zhang

, Zhang

, Filipe

and Cordeiro

(Eds.), Enterprise Information Systems, no 102, Springer Berlin Heidelberg, 2012, pp. 300–314.

Robinson

W.N.

, Pawlowski

S.D.

and Volkov

, Requirements interaction management, ACM Comput Surv 35(2) (2003), 132–190.

Dahlstedt

Å.G.

and Persson

, Requirements interdependencies: State of the art and future challenges, in: Engineering and Managing Software Requirements, Springer, 2005, pp. 95–116.

Carlshamre

, Sandahl

, Lindvall

, Regnell

and Nattoch Dag

, An industrial survey of requirements interdependencies in software product release planning, in: Fifth IEEE International Symposium on Requirements Engineering, 2001 Proceedings, 2001, pp. 84–91.

, Akker

M.V.D.

, Brinkkemper

and Diepen

, An integrated approach for requirement selection and scheduling in software release planning, Requirements Engineering 15(4) (2010), 375–396.

10.

Zhang

, Li

, Zhu

, Jeffery

, Liu

, Wang

and Li

, Investigating dependencies in software requirements for change propagation analysis, Information and Software Technology 56(1) (2014), 40–53.

11.

Karlsson

, Olsson

and Ryan

, Improved practical support for largescale requirements prioritising, Requirements Engineering 2(1) (1997), 51–60.

12.

Carlshamre

, Release planning in market-driven software product development: Provoking an understanding, Requirements Engineering 7(3) (2002), 139–151.

13.

Pitangueira

A.M.

, Maciel

R.S.P.

and Barros

, Software requirements selection and prioritization using sbse approaches: A systematic review and mapping of the literature, Journal of Systems and Software 103 (2015), 267–280.

14.

Ngo

and Saliu

M.O.

, Fuzzy structural dependency constraints in software release planning, in: The 14th IEEE International Conference on Fuzzy Systems, 2005 FUZZ’05, IEEE, 2005, pp. 442–447.

15.

Tang

, Nicholson

, Jin

and Han

, Using bayesian belief networks for change impact analysis in architecture design, Journal of Systems and Software 80(1) (2007), 127–148.

16.

Ngo-The

and Saliu

M.O.

, Measuring dependency constraint satisfaction in software release planning using dissimilarity of fuzzy graphs, in: Cognitive Informatics, 2005(ICCI 2005) Fourth IEEE Conference on, IEEE, 2005, pp. 301–307.

17.

Wang

, Li

, Wang

, Zhang

and Wang

, Asimulation approach for impact analysis of requirement volatility considering dependency change, in: Regnell

and Damian

(Eds.), Requirements Engineering: Foundation for Software Quality, no. 7195, Springer Berlin Heidelberg, 2012, pp. 59–76.

18.

Harman

, Krinke

, MedinaBulo

, PalomoLozano

, Ren

and Yoo

, Exact scalable sensitivity analysis for the next release problem, ACM Trans Softw Eng Methodol 23(2) (2014), 19:1–19:31.

19.

Karlsson

and Ryan

, A costvalue approach for prioritizing requirements, IEEE Software 14(5) (1997), 67–74.

20.

Jung

H.-W.

, Optimizing value and cost in requirements analysis, IEEE Software 15(4) (1998), 74–78.

21.

Ruhe

, Eberlein

and Pfahl

, Trade-off analysis for requirements selection, International Journal of Software Engineering and Knowledge Engineering 13(04) (2003), 345–366.

22.

Baker

, Harman

, Steinhofel

and Skaliotis

, Search based approaches to component selection and prioritization for the next release problem, in: Proceedings of the 22Nd IEEE International Conference on Software Maintenance, IEEE, 2006, pp. 176–185.

23.

Veerapen

, Ochoa

, Harman

and Burke

E.K.

, An integer linear programming approach to the single and bi-objective next release problem, Information and Software Technology 65 (2015), 1–13.

24.

Martello

and Toth

, Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, Inc., New York, NY, USA, 1990.

25.

Mougouei

, Factoring requirement dependencies in software requirement selection using graphs and integer programming, in: Proceedings of the 31st IEEE/ACMInternational Conference on Automated Software Engineering, ACM, 2016, pp. 884–887.

26.

Wolsey

L.A.

, Integer programming, Vol. 42, Wiley New York, 1998.

27.

Mougouei

, Powers

D.M.

and Moeini

, Dependency-aware software release planning, in: Proceedings of the 39th International Conference on Software Engineering (in press), ACM.

28.

Mougouei

and Powers

D.M.

, Dependency-aware software release planning through mining user preferences, arXiv preprint arXiv:1702.05592.

29.

Kalampakas

, Spartalis

, Iliadis

and Pimenidis

, Fuzzy graphs: Algebraic structure and syntactic recognition, Artificial Intelligence Review (2013), 1–12.

30.

Rosenfeld

, Fuzzy graphs, Fuzzy Sets and Their Applications 77 (1975), 95.

31.

Floyd

R.W.

, Algorithm 97: Shortest path, Communications of the ACM 5(6) (1962), 345.

32.

Eells

, Probabilistic causality, Vol. 1, Cambridge University Press, 1991.

33.

Kroese

D.P.

and Chan

J.C.

, et al., Statistical modeling and computation, Springer, 2014.

34.

Macke

J.H.

, Berens

, Ecker

A.S.

, Tolias

A.S.

and Bethge

, Generating spike trains with specified correlation coefficients, Neural Computation 21(2) (2009), 397–423.

35.

Korte

and Vygen

, Combinatorial Optimization: Theory and Algorithms, Springer, 2006.

36.

van den Akker

, Brink

, van Diepen

and Versendaal

, Flexible release planning using integer linear programming, REFSQ’05.

37.

Sagrado

J.D.

, ÃĄguila

I.M.D.

and Orellana

F.J.

. Multiobjective ant colony optimization for requirements selection, Empirical Software Engineering (2013), 1–34.

38.

Boschetti

M.A.

, Golfarelli

, Rizzi

and Turricchia

, A lagrangian heuristic for sprint planning in agile software development, Computers & Operations Research 43 (2014), 116–128.

39.

Greer

and Ruhe

, Software release planning: An evolutionary and iterative approach, Information and Software Technology 46(4) (2004), 243–253.

40.

Bohner

S.A.

, Software change impact analysis..

41.

Wilde

and Huitt

, A reusable toolset for software dependency analysis, Journal of Systems and Software 14(2) (1991), 97–102.

42.

Hapke

, Jaszkiewicz

and Slowinski

, Fuzzy project scheduling system for software development, Fuzzy Sets and Systems 67(1) (1994), 101–117.

43.

Wasserman

and Faust

, Social network analysis: Methods and applications, Vol. 8, Cambridge University Press, 1994.

44.

Zadeh

L.A.

, Fyzzy sets, Inf Comput 8 (1965), 338–353.

45.

De Kleer

and Brown

J.S.

, A qualitative physics based on confluences, Artificial Intelligence 24(1) (1984), 7–83.

46.

Wellman

M.P.

and Derthick

, Formulation of tradeoffs in planning under uncertainty, Pitman London, 1990.

47.

Kusiak

and Wang

, Dependency analysis in constraint negotiation, Systems, Man and Cybernetics, IEEE Transactions on 25(9) (1995), 1301–1313.

48.

Vassilevska

, Williams

and Yuster

, All-pairs bottleneck paths for general graphs in truly sub-cubic time, pp, in: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, ACM, 2007, pp. 585–589.

49.

Racheva

, Daneva

, Sikkel

and Buglione

, Business value is not only dollars–results from case study research on agile software projects, in: Product-Focused Software Process Improvement, Springer, 2010, pp. 131–145.

50.

Villarroel

, Bavota

, Russo

, Oliveto

and Di

, Penta, Release planning of mobile apps based on user reviews, pp, in: Proceedings of the 38th International Conference on Software Engineering, ACM 2016, pp. 14–24.

51.

Sprenger

, Foundations for a probabilistic theory of causal strength.

52.

Halpern

J.Y.

and Hitchcock

, Graded causation and defaults, The British Journal for the Philosophy of Science 66(2) (2015), 413–457.

53.

Pearl

, Causality, Cambridge University Press, 2009.

54.

Janzing

, Balduzzi

, Grosse-Wentrup

and Schölkopf

, et al., Quantifying causal influences, The Annals of Statistics 41(5) (2013), 2324–2358.

55.

Leung

C.W.-K.

, Chan

S.C.-F.

, Chung

F.-L.

and Ngai

, A probabilistic rating inference framework for mining user preferences from reviews, World Wide Web 14(2) (2011), 187–215.

56.

Holland

, Ester

and Kießling

, Preference mining: A novel approach on mining user preferences for personalized applications, in: European Conference on Principles of Data Mining and Knowledge Discovery, Springer, 2003, pp. 204–216.

57.

Sayyad

A.S.

, Menzies

and Ammar

, On the value of user preferences in search-based software engineering: A case study in software product lines, in: 2013 35th International Conference on Software Engineering (ICSE), IEEE, 2013, pp. 492–501.

58.

P.K, Process-Centered Requirements Engineering, Research Studies Pre, Taunton, Somerset, England New York, 1996.

59.

Biffl

, Aurum

, Boehm

, Erdogmus

and Grünbacher

, Value-based software engineering, Vol. 1, Springer, 2006.

60.

Wiegers

K.E.

, Software Requirements, Microsoft Press, 2009.

61.

Cai

, Wei

and Huang

, Evolutionary approaches for multiobjective next release problem, Computing and Informatics 31(4) (2012), 847–875.

62.

Boyd

and Vandenberghe

, Convex optimization, Cambridge University Press, 2004.

63.

Mougouei

, Powers

D.M.W.

and Moeini

, An Integer Linear Programming Model for Binary Knapsack Problem with Dependent Item Values, Springer International Publishing, Cham, 2017, pp. 144–154.

64.

Ibm cplex optimizer - united states (2014). URL http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/

65.

Bellman

and Kalaba

R.E.

, Dynamic programming and modern control theory, Academic Press New York, 1965.

Requirement	r ₁	r ₂	r ₃	r ₄	r ₅	r ₆	r ₇	r ₈	r ₉	r ₁₀	r ₁₁	r ₁₂	r ₁₃	r ₁₄	r ₁₅	r ₁₆	r ₁₇	r ₁₈	r ₁₉	r ₂₀	r ₂₁	r ₂₂	r ₂₃	r ₂₄	r ₂₅	r ₂₆	r ₂₇	Sum
Cost	5.0	20.0	0.0	10.0	1.0	20.0	6.0	5.0	16.0	10.0	4.0	3.0	5.0	7.0	15.0	13.0	14.0	3.0	10.0	7.0	12.0	15.0	8.0	2.0	10.0	0.0	1.0	222.0
Value	10.0	20.0	4.0	17.0	3.0	20.0	15.0	9.0	20.0	16.0	20.0	10.0	6.0	8.0	8.0	10.0	6.0	10.0	20.0	20.0	15.0	20.0	20.0	5.0	0.0	0.0	0.0	312.0