Variable neighborhood descent heuristic for covering design problem

Abstract

In this paper we consider a variable neighborhood descent (VND) heuristic, a variant of variable neighborhood search, for the covering design problem. The neighborhood structures and local search are based on the systematic removing and adding blocks to the covering. We have tested VND search on the greedy coverings and established 13 new best known upper bounds. The proposed approach is also applicable to any covering design.