A tabu search algorithm for the covering design problem

A tabu search algorithm for the covering design problem

0.00 Avg rating0 Votes
Article ID: iaor201111622
Volume: 17
Issue: 6
Start Page Number: 659
End Page Number: 674
Publication Date: Dec 2011
Journal: Journal of Heuristics
Authors: ,
Keywords: heuristics: tabu search
Abstract:

A (v,k,t)‐covering design is a collection of k‐subsets (called blocks) of a v‐set 𝒱 equ1 such that every t‐subset of 𝒱 equ2 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.

Reviews

Required fields are marked *. Your email address will not be published.