ILS-VND Algorithm for the Maximum Intersection Problem of k-Subsets

Given a collection L of n subsets of a set R of elements, the Maximum Intersection Problem of k-Subsets (kMIS) consists of finding L' ⊆ L with |L'| = k such that the intersection of the subsets at L' is maximum. This work proposes an Iterated Local Search (ILS) meta-heuristic for kMIS. It uses two neighbourhood structures, exploited via a Variable Neighbourhood Descent (VND) strategy with innovative use of data structures to speed up the local search phase, thereby improving performance. The computational tests prove the superiority of this proposal in relation to the algorithms in the literature, finding on average solutions of higher quality than those of the state of the art.