Speaker: John Stardom, recent MSc, Simon Fraser University Time: Tuesday, October 30, at 14:30 Place: MCD 318 (MacDonald Hall), SITE, University of Ottawa Title: Metaheuristics and the Search for Covering Arrays Abstract: A strength 2 covering 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 (x,y) from the g-ary alphabet, there exists at least one row r such that a_{ri}=x and a_{rj}=y. The problem of interest is to determine the minimum number b of rows for which a (b x k) covering array with entries from the g-ary alphabet exists, where k and g are given. Upper bounds on the size of covering arrays are constantly being improved through the discovery of new constructions. Randomized searches can also be used to find new arrays through the use of metaheuristics that are widely applicable to a number of combinatorial problems. We search for covering arrays using simulated annealing, tabu and genetic search algorithms and attempt to draw conclusions about their suitability to the task at hand. 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 to this problem including a complete solution to the four-column case.