Submitted by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2016-02-17T11:41:50Z
No. of bitstreams: 1
arquivototal.pdf: 1276201 bytes, checksum: 9dd8fad80c483276a40101ee6a782d5b (MD5) / Made available in DSpace on 2016-02-17T11:41:50Z (GMT). No. of bitstreams: 1
arquivototal.pdf: 1276201 bytes, checksum: 9dd8fad80c483276a40101ee6a782d5b (MD5)
Previous issue date: 2015-07-21 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work deals with the p-Cluster Editing Problem (p-CEP), which consists in performing
a minimum number of editions (additions or removals of edges) in a graph G in
order to transform it in a disjoint union of p cliques (clusters), where G and p are input
data. p-CEP is a NP-Hard problem with applications in areas such as computational
biology and machine learning. To solve this problem, we propose two new mathematical
formulations and improvements in a formulation from the literature, as well as new valid
inequalities. The three formulations were studied both theoretically, by comparing their
linear relaxations, and practically, by implementing three exact algorithms: two based on
Branch-and-Cut (BC) and one based on Branch-and-Price (BP). The proposed algorithms
were tested in instances with up to 211 vertices. The results show the performance of
the algorithms according to the graph density and the ratio between p and the number
of vertices. Overall, the BC algorithms were superior to the BP algorithm. However, the
latter obtained the best dual bounds in some instances. / Este trabalho trata do Problema de Edi¸c˜ao de p-Clusters (p-PEC), o qual consiste em
realizar um n´umero m´ınimo de edi¸c˜oes (adi¸c˜oes ou remo¸c˜oes de arestas) em um grafo G
de modo a transform´a-lo em uma uni˜ao disjunta de p cliques (ou clusters), sendo G e p
dados de entrada. O p-PEC ´e um problema NP-Dif´ıcil que possui aplica¸c˜oes em ´areas
como biologia computacional e aprendizagem de m´aquina. Para resolvˆe-lo, foram propostas
duas novas formula¸c˜oes matem´aticas e melhorias em uma formula¸c˜ao proveniente da
literatura, bem como novas desigualdades v´alidas. As trˆes formula¸c˜oes consideradas foram
estudadas tanto teoricamente, atrav´es da compara¸c˜ao entre as relaxa¸c˜oes lineares, quanto
empiricamente, atrav´es do desenvolvimento de trˆes algoritmos exatos: dois baseados em
Branch-and-Cut (BC) e um baseado em Branch-and-Price (BP). Os algoritmos foram testados
em instˆancias com at´e 211 v´ertices. Os resultados mostram o impacto da raz˜ao entre
p e o n´umero de v´ertices, da densidade do grafo e das desigualdades nos desempenhos dos
algoritmos. No geral, os algoritmos BC foram superiores ao algoritmo BP. Por´em, em
algumas instˆancias, os melhores limites duais foram obtidos pelo algoritmo BP.
| Identifer | oai:union.ndltd.org:IBICT/oai:tede.biblioteca.ufpb.br:tede/7870 |
| Date | 21 July 2015 |
| Creators | Cabral, Lucidio dos Anjos Formiga |
| Contributors | Subramanian, Anand |
| Publisher | Universidade Federal da Paraíba, Programa de Pós-Graduação em Informática, UFPB, Brasil, Informática |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFPB, instname:Universidade Federal da Paraíba, instacron:UFPB |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 4679641312648529202, 600, 600, 600, 600, 7879657947546587587, 3671711205811204509, 2075167498588264571 |
Page generated in 0.0025 seconds