USO DE TÉCNICAS DE LINEARIZAÇÃO NA OBTENÇÃO DE MODELOS DE PROGRAMAÇÃO LINEAR INTEIRA PARA O PROBLEMA DA DIVERSIDADE MÁXIMA DE GRUPOS

O Problema da Diversidade Máxima de Grupos (PDMG) consiste em agrupar um determinado conjunto de $n$ elementos em $m$ grupos disjuntos, de modo que a diversidade, obtida pela soma das distâncias individuais entre cada par de elementos, em cada grupo seja a maior possível. O problema é NP-Difícil e por isso diversas pesquisas têm focado em encontrar soluções através de heurísticas e meta-heurísticas. Na direção oposta das soluções aproximadas, outras pesquisas têm focado na construção de modelos matemáticos para o PDMG. Neste trabalho, dois novos modelos matemáticos de programação linear inteira, para o PDMG, são obtidos através da aplicação de técnicas de linearização de funções quadráticas. Os modelos gerados são comparados, por meio de experimento computacional, em $240$ instâncias da literatura, com outro modelo também linearizado e inteiro da literatura. Os resultados mostram que um dos novos modelos obtido alcançou os melhores valores em termos de tempo computacional e GAP.