The Next Release Problem
This page is to present some supplement materials of the Next Release Problem (NRP) and the Backbone based Multilevel Algorithm (BMA). In this page, we list five items about the NRP and the BMA in our work.
  • Two sets of the NRP instances
  • A brief technical report, about the complexity analysis for the NRP backbone
  • A brief technical report, about the pseudo code of two typical algorithms
  • A brief technical report, about the parameter tuning of an algorithm
  • Our paper in IEEE Transactions on Software Engineering
  • Correction of original Table 9 in our published paper
The Next Release Problem (NRP) has been proposed to model the decision for customer profits and requirements costs in requirements engineering. The NRP seeks to maximize customer profits from a set of dependent requirements, under the constraint of a predefined budget bound. Assisted by the NRP, a requirements engineer can make a decision for software requirements to balance the profits of the company and the customers.
In this page, we provide two sets of problem instances. One set consists of the classic instances, which are generated from the literature; the other set consists of the realistic instances, which are mined from open bug repositories.
These NRP instances can be downloaded here, the classic NRP instances and the realistic NRP instances . Note that the format of instances in the two data sets are not the same. In each zip file, a readme file is included to describe the format of the instances.
Note that all the files are text files in Windows Compatible Format. If you want to read these instances in Linux, Unix, or Mac, you should convert the \n\r in each line into \n (for Linux), \n (for Unix), or \r (for Mac).
The brief technical report of the complexity analysis for the backbone in BMA is Complexity analysis for the NRP backbone . In this report, we present why it is NP-hard to obtain the NRP backbone.
The brief technical report of the pseudo code of a Genetic Algorithm (GA) and Multi-Start strategy based Simulated Annealing algorithm (MSSA) is Pseudo code of GA and MSSA . In this report, we present the details for some readers, who are interested in the implementations of these two algorithms. The pseudo code of BMA can be found in our paper.
The brief technical report of the parameter tuning of Multi-Start strategy based Simulated Annealing algorithm (MSSA) is Parameter tuning of MSSA . In this report, we present the details for visualized tuning of the parameter of MSSA. In MSSA,a non-linear Simulated Annealing algorithm (SA) is employed as a local search operator. In the process of parameter tuning, the slope of a tendency line shows the profit rate, which is provided when increasing the running time. Thus, we chose the tendency lines, which can provide the largest slopes.
There exists a data mistake in the original Table 9 in our published paper as follows. We are sorry for this mistake. It appears in the second column, called Bound: the data in this column were disordered. The corrected version can be found in Correction of Table 9. We greatly thank Dr. Wu Song, with the Hainan Tropical Ocean University for pointing out the mistake. Note that this mistake will not hurt any other data in our paper and will not hurt any other published paper based on our dataset. We highlight the way of calculating the bound in Table 9 again, as mentioned in our paper. The bound is defined as follows: the sum of all costs of requirements multiplies the ratio, where the ratio equals to 0.3 or 0.5, as suggested in Table 9.
If anything in this page is useful to you, please cite our paper in IEEE Transactions on Software Engineering.
Jifeng Xuan, He Jiang, Zhilei Ren, Zhongxuan Luo. Solving the Large Scale Next Release Problem with a Backbone Based Multilevel Algorithm. IEEE Transactions on Software Engineering, vol. 38, no. 5, Sept.-Oct. 2012, pp. 1195-1212. [PDF], [IEEE]
If you have any question about our data sets or our paper, please contact Jifeng Xuan, State Key Lab of Software Engineering, Wuhan University.
E-mail: xuan (at) whu (dot) edu (dot) cn