Tabu search for covering arrays using permutation vectors

A covering array  CA(N;t,k,v)$\mathsf{CA}(N;t,k,v)$ is an N×k$N\times k$ array, in which in every N×t$N\times t$ subarray, each of the v^t$v^t$ possible t  -tuples over v$v$ symbols occurs at least once. The parameter t is the strength   of the array. Covering arrays have a wide range of applications for experimental screening designs, particularly for software interaction testing. A compact representation of certain covering arrays employs “permutation vectors” to encode v^t×1$v^t\times 1$ subarrays of the covering array so that a covering perfect hash family whose entries correspond to permutation vectors yields a covering array. We introduce a method for effective search for covering arrays of this type using tabu search. Using this technique, improved covering arrays of strength 3, 4 and 5 have been found, as well as the first arrays of strength 6 and 7 found by computational search.