An Integer Linear Programming approach to the single and bi-objective Next Release Problem

Citation

Veerapen N, Ochoa G, Harman M & Burke E (2015) An Integer Linear Programming approach to the single and bi-objective Next Release Problem. Information and Software Technology, 65, pp. 1-13. https://doi.org/10.1016/j.infsof.2015.03.008

Abstract
Context The Next Release Problem involves determining the set of requirements to implement in the next release of a software project. When the problem was first formulated in 2001, Integer Linear Programming, an exact method, was found to be impractical because of large execution times. Since then, the problem has mainly been addressed by employing metaheuristic techniques.  Objective In this paper, we investigate if the single-objective and bi-objective Next Release Problem can be solved exactly and how to better approximate the results when exact resolution is costly.  Methods We revisit Integer Linear Programming for the single-objective version of the problem. In addition, we integrate it within the Epsilon-constraint method to address the bi-objective problem. We also investigate how the Pareto front of the bi-objective problem can be approximated through an anytime deterministic Integer Linear Programming-based algorithm when results are required within strict runtime constraints. Comparisons are carried out against NSGA-II. Experiments are performed on a combination of synthetic and real-world datasets. Findings We show that a modern Integer Linear Programming solver is now a viable method for this problem. Large single objective instances and small bi-objective instances can be solved exactly very quickly. On large bi-objective instances, execution times can be significant when calculating the complete Pareto front. However, good approximations can be found effectively.  Conclusion This study suggests that (1) approximation algorithms can be discarded in favor of the exact method for the single-objective instances and small bi-objective instances, (2) the Integer Linear Programming-based approximate algorithm outperforms the NSGA-II genetic approach on large bi-objective instances, and (3) the run times for both methods are low enough to be used in real-world situations.

Keywords
Integer Linear Programming; Multi-objective optimization; Next Release Problem; Requirements optimization; Search based software engineering

Journal
Information and Software Technology: Volume 65

People

Professor Gabriela Ochoa

Professor, Computing Science