CanaDAM 2019
SFU Harbour Centre, May 29 - 31, 2019

Covering Arrays - Part I
Org: Lucia Moura (University of Ottawa) and Brett Stevens (Carleton University)

YASMEEN AKHTAR, Arizona State University, USA
Constructing High Index Covering Arrays and Their Application to Design of Experiments  [PDF]

A high index covering array ($CA_{\lambda}$) has the property that the measurements of all $t$-tuples from any $t$ factors are guaranteed to be repeated at least $\lambda$ times, where the index $\lambda>1$ is an adjustable parameter that depends on the experimental resource. We develop a systematic method to construct the (supersaturated) $CA_{\lambda}$ of strength $t\leq 3$ with small run sizes under the different number of factors and index. Using a small number of runs compared to the orthogonal arrays, a $CA_{\lambda}$ provides the resistance towards outlying measurements which a covering array ($\lambda =1$) fails to do.

MYRA B. COHEN, Iowa State University
Learning to Build Covering Arrays with Hyperheuristic Search  [PDF]

Today there are a large number of techniques and tools to build covering arrays. Some of the algorithms are optimized for constrained or unconstrained variants of the problem, or work best on specific symbol sizes or strengths. Yet, no one strategy fits all. In this work we introduce a hyperheuristic algorithm that learns strategies for building covering arrays providing a single generalist approach. Our experiments show that our algorithm competes with known best search algorithms across 85 constrained and unconstrained problems from the software testing domain. For most of the models, hyperheuristic search is as good as, or improves upon the best known search results. We also present some evidence that our algorithm's strong generic performance is the result of unsupervised learning.

KIRSTEN NELSON, Carleton University
Constructing covering arrays from interleaved sequences  [PDF]

Interleaved sequences over a finite field in array form have columns that are either zero columns or phase shifts of a shorter sequence. Shift sequences give a compact representation of an interleaved sequence, given the base sequence. We are interested in whether sequences that are useful for building covering arrays can be lengthened through the choice of an appropriate shift sequence. We give some preliminary results on what properties of base sequences are preserved in the interleaved sequence, discuss an equivalence relation on shift sequences to reduce the search space, and finally show some potential usefulness of the construction.

BRETT STEVENS, Carleton University
Introduction to covering arrays  [PDF]

As a preface to the minisympoisum on covering arrays I will introduce covering arrays formally and by example. I will discuss the central construction methods including recursive, algebraic and probabilistic. I will review known optimal arrays and asymptotic sizes. I will end with some open problems.