Resumo: A classificação de dados consiste em separar um conjunto de objetos, descritos por um conjunto de dados, em classes, de forma a que objetos na mesma classe sejam semelhantes entre si. A classificação freqüentemente é usada como uma ferramenta de pesquisa científica. Os objetivos de uma classificação podem diferir de acordo com as necessidades e com a origem dos dados sobre os objetos a classificar. Em alguns contextos existe interesse em associar os objetos aos vértices de um grafo, de forma que a semelhança entre os objetos esteja relacionada a proximidade nesse grafo. Os métodos existentes, para aplicações nestes contextos~ obrigam cada classe a formar um único componente conexo dentro do grafo. Chamamos essa abordagem de conexidade estrita e propomos a idéia de classificação com conexidade flexibilizada, ou seja a concepção de métodos que permitam a um usuário especificar o número de componentes de cada classe no grafo e mostramos porque essa flexibilização é desejável. Em seguida, estudamos a resolução de um problema computacional resultante da flexibilização da conexidade, o Problema da Atribuição ?-Conexa (PAgC). Demonstramos a NP-completude desse problema e apontamos alguns casos polinomiais. Então, concentramo-nos no estudo de diferentes formas para modelar matematicamente a conexidade flexibilizada. Os resultados obtidos podem ser naturalmente aplicados a outros problemas onde tal conexidade é necessária. Finalmente, propomos dois algoritmos para resolver (PAgC). Um baseado na técnica de branch-and-bound e outro na de branch-and-price. Uma comparação dos resultados obtidos por cada técnica é apresentada na seqüência. em estudo de classes de desigualdades válidas, capazes de melhorar substancialmente ambos os algoritmos, conclui a dissertação. Ver menos

Abstract: Classification of objects amounts to defining, say, K clusters on a set of N objects such that object in a same cluster are alike. Classification is often used as a tool for scientific research. Some important contexts of objects classification use enhanced methods where the objects are associated to vertices of a graph. Proximity between two objects in this graph usually means that the dissimilarity between them is small. The methods applied in such contexts require each cluster to define a single connected component on this graph. We call this strict connectivity approach and we propose the idea of flexible connectivity. This suggests the development of methods where the user may specify the number of connected components each cluster may form on the graph. We present reasons for this flexibilization. Next, we study the computational problem derived from the flexible connectivity, the y-Connected Assignment Problem (PAgC). We show this problem to be NP-complete and we point out some polynomial cases. Then, we concentrate our effort on deriving formulations for considering this flexible connectivity. Clearly, the conceived models can be applied to other problems where connectivity constraints are to be considered. Finally, we propose two algorithms to solve PAgC. One based on the branch-and-cut technique and other on the branch-and-price technique. A comparison between the results obtained with each technique is presented. We conclude this work studying classes of valid inequalities capable of improving the efficiency of both algorithms. Ver menos