Um algoritmo exato para o problema da diversidade máxima

• Ano de defesa: 2011
• Autor(a) principal: Bruno Takane
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Minas Gerais; UFMG
• Palavras-chave em Português: Técnica de Reformulação de Linearização; Problema da Diversidade Máxima; Método de Decomposição de Benders; Método de decomposição; Engenharia de produção
• Link de acesso: http://hdl.handle.net/1843/BUOS-8S4KLF

The term diversity is related to the variety of features, ideas or differents elements among them within a given context, being important for the pluralism, heterogeneity, mutual tolerance and survival of ideas. There are several types o fdiversity in different areas of human knowledge. Among them, we can mentios religious, social, linguistic, sexual, cultural and biological diversity. In the context of combinatorial optimization, the Maximum Diversity Problem (MDP) consists of selecting a subset of m elements from a set of n elements in such a way that the diversity among the selected elements is maximized. Anew model for this problem is presented in this work based on the Reformulation- Linearization-Technique. Due to the characteristics of the proposed formulation and the difficulty of this resolution, the Revised Benders Decomposition Method is applied to the problem and a pre-processing technique is used in order to accelerate its convergence. Tests are performed to evaluate the performance of the method applied to the problem and then an analysis is done comparing it with another algorithm described in the literature. The computational results show that the presented method shows to be competitive with the exact methods described in the literature