Problema de recobrimento de conjuntos com agrupamento: modelos e algoritmos

Abstract

This work addresses the clustered set covering problem, a variant of the classic set covering problem in which sets are arranged in K disjoint clusters. Two practical applications found in the literature are presented. The first originates from electrical engineering, specifically from the problem addressed by Fritzen et al. (2012). An intrinsic characteristic of this problem led to a generalization in set allocation, so that the intersection between clusters is allowed. The second application comes from the mining industry and is owed to Bilal et al. (2014). They proposed a set of instances and a metaheuristic based on iterated tabu search (ITS). Regarding solution methods, the first contribution of this work is a mathematical formulation with column generation, used in order to obtain upper bounds for the instances. Two other contributions refer to the ITS metaheuristic, with the former consisting in a parallel approach for the tabu search component, while the latter resides in the addition of a neighborhood solved with integer programming and based on hard variable fixing. The idea behind the addition of the neighborhood is to occupy the time saved by the parallel approach with the improvement of promising solutions obtained by tabu search. The computational results show improvements in solution quality for the vast majority of instances. Moreover, given the magnitude of the costs involved in the problem, it is possible to conclude that the improvement of ITS metaheuristic with the contributions presented in this work can provide significant economic benefit.