Algoritmo ILS-VND para o Problema da Interseção Máxima de k-Subconjuntos

Dada uma coleção L de n subconjuntos de um conjunto R de elementos, o Problema da Interseção Máxima de k-Subconjuntos (kMIS) consiste em encontrar L' ⊆ L com |L'| = k tal que a interseção dos subconjuntos em L' seja máxima. Este trabalho propõe uma meta-heurística Iterated Local Search (ILS) para o kMIS. Ela utiliza duas estruturas de vizinhança, exploradas via uma estratégia Variable Neighborhood Descent (VND) com uso inovador de estruturas de dados para acelerar a fase de busca local, melhorando, assim, a performance. Os testes computacionais comprovam a superioridade desta proposta em relação aos algoritmos da literatura, encontrando em média soluções de qualidade superior às do estado da arte.