A Multilevel Cooperative Tabu Search Algorithm for the Covering Design Problem

Abstract

We propose a multilevel cooperative search algorithm to compute upper bounds for $C_{\lambda }(v,k,t)$, the minimum number of blocks in a $t-(v,k,\lambda )$ covering design. Multilevel cooperative search is a search heuristic combining cooperative search and multilevel search. We first introduce a coarsening strategy for the covering design problem which defines reduced forms of an original $t-(v,k,\lambda )$ problem for each level of the multilevel search. A new tabu search algorithm is introduced to optimize the problem at each level. Cooperation operators between tabu search procedures at different levels include new re-coarsening and interpolation operators. We report the results of tests that have been conducted on $158$ covering design problems. Improved upper bounds have been found for $34$ problems, many of which exhibit a tight gap. The proposed heuristic appears to be a very promising approach to tackle other similar optimization problems in the field of combinatorial design.