A large neighbourhood search heuristic for covering designs

Abstract

In this paper, we propose a new heuristic for the covering design problem based on a large neighbourhood search (LNS) metaheuristic that can be seen as a special case of a variable neighbourhood search. As the initial solution, we use a well-known greedy heuristic as well as a new tie-braking rule within greedy algorithms for choosing blocks in the covering. Some theoretical aspects of the greedy heuristic are discussed. The proposed LNS-based heuristic called level reduction can be applied to any covering design and different pre-defined orders, such as lex, colex, etc. With our simple approach, we establish 21 new best known upper bounds on the covering number.