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
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.
Keywords: covering design | greedy | large neighbourhood search | variable neighbourhood search
Publisher: Oxford University Press

Show full item record

SCOPUSTM   
Citations

2
checked on Apr 15, 2021

Page view(s)

9
checked on Apr 16, 2021

Google ScholarTM

Check

Altmetric

Altmetric


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