|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
checked on Apr 15, 2021
checked on Apr 16, 2021
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.