Metaheuristic post-optimization of the NIST repository of covering arrays

Construction of Covering Arrays (CA) with minimum possible number of rows is challenging. Often the available CA have redundant combinatorial interaction that could be removed to reduce the number of rows. This paper addresses the problem of removing redundancy of CA using a metaheuristic post-optimization (MPO) approach. Our approach consists of three main components: a redundancy detector (RD); a row reducer (RR); and a missing-combinations reducer (MCR). The MCR is a metaheuristic component implemented using a simulated annealing algorithm. MPO was instantiated with 21,964 CA taken from the National Institute of Standards and Technology (NIST) repository. It is a remarkable result that this instantiation of MPO has delivered 349 new upper bounds for these CA.