Menu
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.