| We propose a multilevel cooperative parallel tabu search (MCPTS) algorithm to compute upper bounds for Clambda( v, k, t), the minimum number of blocks of an instance t - (v, k, lambda) of a covering design problem. 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 instance for each level of the multilevel search. A new parallel tabu search algorithm is introduced to optimize the problem instance of each level. Cooperation operators between parallel 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 problem instances. Improved upper bounds have been found for 26 problem instances, many of which with tight gap between the lower and upper bounds. The proposed algorithm appears to be a very promising approach to tackle other similar optimization problems in the field of combinatorial designs. |
