Evaluation of Tie-Breaking and Parameter Ordering for the IPO Family of Algorithms Used in Covering Array Generation

摘要

The IPO (In-Parameter-Order) family of algorithms is a popular set of greedy methods for the construction of covering arrays. Aspects such as tie-breaking behavior or parameter ordering can have major impact on the quality of the resulting arrays but have so far not been studied in a systematic manner. In this paper, we survey and present a general framework for the IPO family of algorithms (i.e. IPOG, IPOG-F and IPOG-F2) and present ways to instantiate these abstract components. Then, we evaluate the performance of these variations on a large set of instances, in an extensive experimental setting in terms of covering array sizes.