Exact scalable sensitivity analysis for the next release problem

摘要

The next release problem (NRP) is part of the search-based software engineering (SBSE) paradigm. SBSE studies algorithms that find solutions to software developers' problems. The original NRP (2001) was to select the best set of requirements to tackle in the next release of a product. Given estimates of costs and revenues, the objective is to maximize revenue within budget. This paper studies the special case of independent requirements. It shows how to discover costs, revenues, and budgets that have a big effect on the outcome. The paper shows that the Nemhauser-Ullmann algorithm has the predicted polynomial mean time and is fast enough on practical examples to be run many times to discover sensitive cases. The authors note that pathological cases lead to the exponential worst cases of an NP-hard problem. They do not say that using randomization handles such problems in practice. They test their algorithm on the Motorola dataset, but give no source.