Busca de Agrupamentos de Dados Utilizando Geração de Colunas em Programação Inteira

In this work, we present ourselves two exact models based on technique generation of columns for problem on grouping graphs known as k-cluster, where the goal and partition a given graph G(V;E), k-components (subgraphs) connected in such a way that the sum of the edges within each component is minimum. Our models were inspired by problems of flow in networks to ensure connectivity of subgraphs representing the groups. The two models linear and integer, have been termed OneFlow, based on the construction of a single stream and Multiflow, based on the construction of multiple streams. Was used column generation method justified by the combinatorial characteristic and the high number of variables (and hence columns) associated with each instance of problem k-cluster. To generate the initial set of columns, we apply a modified version of the approximation algorithm proposed by Saran and Vazirani for the resolution of the problem min k-cut. In this strategy, we started from a tree Gomory-Hu for the input graph G and successively applied  greedy way cuts up to k associated cutting with the  edges of the tree Gomory-Hu. To obtain the integer solutions was used branch-and-bound technical . For the stage of branch, we used the strategy proposed by Ryan and Foster, thereby obtain branching tree generated which tend to be more balanced than those generated by the imposition of successive integral to each of the variables.