Empirically Identifying the Best Greedy Algorithm for Covering Array Generation

Covering array generation is a key issue in combinatorial testing. A number of researchers have been applying greedy algorithms for covering array construction. A greedy framework has been built to integrate most greedy algorithms and evaluate new approaches derived from this framework. However, this framework is affected by multiple factors, which makes its deployment and optimization very challenging. In order to identify the best configuration, we propose a search method that combines pairwise coverage with either base choice or hill climbing techniques. We conduct three different groups of experiments based on six decisions of the greedy framework. The influence of these decisions and their interactions are studied systematically, and the selected greedy algorithm for covering array generation is shown to be better than the existing greedy algorithms.