Upper bounds for covering arrays by tabu search

A t-covering array is a collection of k vectors in a discrete space with the property that, in any t coordinate positions, all combinations of the coordinate values occur at least once. Such arrays have applications, for example, in software testing and data compression. Covering arrays are sometimes also called t-surjective arrays or qualitatively t-independent families; when t = 2 covering arrays are also called group covering designs or transversal covers. In an optimal covering array the number of vectors is minimized. Constructions for optimal covering arrays are known when t = 2 and the vectors are binary vectors, but in the other cases only upper and lower bounds are known. In this work a tabu search heuristic is used to construct covering arrays that improve on the previously known upper bounds on the sizes of optimal covering arrays. (C) 2003 Elsevier B.V. All rights reserved.