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.
Published
2016
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.