Approximate Backbone Based Multilevel Algorithm for Next Release Problem
This addresses the lack of efficient approximate algorithms for large-scale NRP instances in software requirement engineering, representing an incremental improvement.
The paper tackled the NP-hard Next Release Problem (NRP) for selecting software requirements to maximize profits by proposing an approximate backbone based multilevel algorithm (ABMA), which outperformed existing algorithms on large instances in terms of solution quality and running time.
The next release problem (NRP) aims to effectively select software requirements in order to acquire maximum customer profits. As an NP-hard problem in software requirement engineering, NRP lacks efficient approximate algorithms for large scale instances. The backbone is a new tool for tackling large scale NP-hard problems in recent years. In this paper, we employ the backbone to design high performance approximate algorithms for large scale NRP instances. Firstly we show that it is NP-hard to obtain the backbone of NRP. Then, we illustrate by fitness landscape analysis that the backbone can be well approximated by the shared common parts of local optimal solutions. Therefore, we propose an approximate backbone based multilevel algorithm (ABMA) to solve large scale NRP instances. This algorithm iteratively explores the search spaces by multilevel reductions and refinements. Experimental results demonstrate that ABMA outperforms existing algorithms on large instances in terms of solution quality and running time.