Authors: Nikolić, Nebojša
Grujičić, Igor
Mladenović, Nenad 
Title: A large neighbourhood search heuristic for covering designs
Journal: IMA Journal of Management Mathematics
Volume: 27
Issue: 1
First page: 89
Last page: 106
Issue Date: 1-Jan-2016
Rank: M22
ISSN: 1471-678X
DOI: 10.1093/imaman/dpu003
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.
Keywords: covering design | greedy | large neighbourhood search | variable neighbourhood search
Publisher: Oxford University Press

Show full item record


checked on Apr 15, 2021

Page view(s)

checked on Apr 16, 2021

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.