An effective formulation of the multi-criteria test suite minimization problem

Abstract

Test suite minimization problem has been mainly addressed by employing heuristic techniques or integer linear programming focusing on a specific criterion or bi-criteria. These approaches fall short to compute optimal solutions especially when there exists overlap among test cases in terms of various criteria such as code coverage and the set of detected faults. Nonlinear formulations have also been proposed recently to address such cases. However, these formulations require significantly more computational resources compared to linear ones. Moreover, they are also subject to shortcomings that might still lead to sub-optimal solutions. In this paper, we identify such shortcomings and we propose an alternative formulation of the problem. We have empirically evaluated the effectiveness of our approach based on a publicly available dataset and compared it with respect to the state-of-the-art based on the same objective function and the same set of criteria including statement coverage, fault-revealing capability, and test execution time. Results show that our formulation leads to either better results or the same results, when the previously obtained results were already the optimal ones. In addition, our formulation is a linear formulation, which can be solved much more efficiently compared to non-linear formulations.