Programação Matemática Aplicada ao Problema de Clusterização com Aplicação em Engenharia de Software

 O problema de clusterização tem uma importante aplicação na Engenharia de Software, a qual muitas vezes lida com grandes sistemas que possuem estruturas ricas e complexas. Para facilitar o trabalho dos profissionais que mantêm os  softwares, e os componentes destes sistemas são divididos em grupos de tal modo que os grupos formados tenham módulos com alto grau de relacionamento e em grupos distintos sejam alocados módulos que possuem pequena relação entre si. A medida utilizada para analisar a qualidade da partição de um sistema é chamada de Qualidade de  Modularização (Modularization Quality - MQ). Modeladores representam o sistema do software, como um grafo, onde os vértices representam os módulos e as relações  entre os módulos são representados por arestas. Este grafo  é conhecido na literatura como Grafo Dependente Modular (Module Dependency Graph - MDG). O Problemade Clusterização de Software (PCS) consiste em encontrar uma partição para o MDG que maximize a Trubo MQ. Nesta tese, utilizamos programação matemática para obter a solução  ótima do PCS. Primeiro formulamos o PCS como um problema de soma de funções fracionárias lineares, em seguida são aplicados dois procedimentos de linearização para reformular o PCS de duas formas diferentes de problema de programação linear inteira mista. Propomos um método de pré-processamento que reduz o tamanho do problema original e também apresentamos desigualdades válidas que se mostram eficientes em deixar as formulações mais fortes. De nosso  conhecimento, esta é a primeira vez que um modelo de programação matemática é proposto para o PCS.  Apresentamos resultados numéricos que comparam as formulações aqui propostas e comparam nossos resultados com as soluções obtidas por outros algoritmos da literatura em problemas benchmark.