A tabu search algorithm for the covering design problem

A (v,k,t)-covering design is a collection of k-subsets (called blocks) of a v-set V{\mathcal{V}} such that every t-subset of V{\mathcal{V}} is contained in at least one block. Given v, k and t, the goal of the covering design problem is to find a covering made of a minimum number of blocks. In this paper, we present a new tabu algorithm for tackling this problem. Our algorithm exploits a new implementation designed in order to evaluate efficiently the performance of the neighbors of the current configuration. The new implementation is much less space-consuming than the currently used technique, making it possible to tackle much larger problem instances. It is also significantly faster. Thanks to these improved data structures, our tabu algorithm was able to improve the upper bound of more than 50 problem instances.