Aplicação da Técnica de Agregação de Restrições para Agrupamento de Dados pela Soma Mínima de Distâncias Quadráticas
otimização de grande porte; clustering; data mining
A geração de colunas é uma abordagem bem conhecida para resolver problemas de otimização em grande escala. Entretanto, este método pode perder rendimento devido à presença de degeneração. A técnica de agregação dinâmica de restrições foi proposta por Elhallaoui et al.noOperations Research 2005; 53: 632–45 e está sendo utilizada por alguns autores para superar essa desvantagem. A idéia por trás dessa técnica é criar uma política para agregar as restrições do problema mestre e gerar colunas de forma controlada, de acordo com a agregação em utilização. O problema de agrupamento de dados pela soma mínima de distâncias quadráticas consiste em, dado um conjunto C de pontos no espaço Euclidiano, particionar C em K clusters (subconjuntos) de forma que a soma das distâncias quadráticas entre cada ponto e o centroide do grupo ao qual ele pertence seja minimizada. Recentemente, Aloise et al no Math. Program. 2012; 131:195-220 propuseram um algoritmo, baseado em argumentos geométricos, para resolver o problema auxiliar durante a geração de colunas. Essa melhoria permitiu encontrar pela primeira vez soluções para instâncias com mais de 2.300 pontos. Nesse contexto, o objetivo do trabalho é combinar as duas técnicas supracitadas a fim de resolver de forma ótima o problema de agrupamento de dados pela soma mínima de distâncias quadráticas em instâncias ainda maiores.