Metaheuristics and the search for covering and packing arrays

A strength 2 covering array (packing array) is an array with k columns and entries from a g-ary alphabet such that given any two columns i and j and any ordered pairs of elements (g1, g 2) from the g-ary alphabet, there exists at least (at most) one row r such that ari = g1 and arj = g2. The problem of interest is to determine the minimum (maximum) number b of rows for which a b x k covering (packing) array with entries from the g-ary alphabet exists, where k and g are given.; The primary application of covering arrays is that of software and network testing. In order to construct arrays which are fully applicable to software and network tests of any flavour, it is necessary to consider arrays where each column possesses its own alphabet size. We present some initial results for this problem, including a complete solution for the case k = 4. (Abstract shortened by UMI.)...