| A (v, k; t)-covering design is a collection of k-subsets (called blocks) of a v-set V such that every t-subset of 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 with a mechanism of diversification and a new memetic algorithm for the solution of the problem. Our algorithms use a new implementation totally incremental 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 (between 10 and 100 times faster) and the speeding rate gets higher and higher as the size of the instances raises. We measured the performance of our tabu algorithm trying more than 700 problem instances. Thanks to the improved data structures, our tabu algorithm was able to improve the upper bound of 77 problem instances and still hold the record for 71 of them. |
