Reactive VNS algorithm for the maximum k-subset intersection problem

Fabio C. S. Dias (), Wladimir Araújo Tavares () and José Robertty de Freitas Costa ()
Additional contact information
Fabio C. S. Dias: Federal University of Ceará
Wladimir Araújo Tavares: Federal University of Ceará
José Robertty de Freitas Costa: Federal University of Ceará

Journal of Heuristics, 2020, vol. 26, issue 6, No 6, 913-941

Abstract: Abstract This paper proposes a reactive VNS metaheuristic for the maximum intersection of k-subsets problem (kMIS). The kMIS is defined as: Given a set of elements, a subset family of the first set and an integer k. The problem consists of finding k subset so that the intersection is maximum. Our VNS metaheuristic incorporates strategies used in GRASP metaheuristics, such as the GRASP construction phase and the Reactive GRASP. Both were used in the shaking phase as a reactive components to VNS. We also propose what we call teh Dynamic Step, a new way to increase the VNS neighborhood. All of these strategies, as well as the Skewed VNS, were added to our Reactive VNS algorithm for kMIS. Computational results showed that the new algorithm outperforms the state-of-the-art algorithm.

Keywords: Reactive VNS; Metaheuristics; Heuristics; Maximum intersection of k-subsets problem (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-020-09452-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:26:y:2020:i:6:d:10.1007_s10732-020-09452-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-020-09452-y

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().