Programa de Pós-Graduação em Ciência da Computação. Departamento de Computação, Universidade Federal de Ouro Preto. / Submitted by giuliana silveira (giulianagphoto@gmail.com) on 2016-02-16T17:53:54Z
No. of bitstreams: 1
DISSERTAÇÃO_AlgorismosExatosHeurísticos.pdf: 1324128 bytes, checksum: d6be4d92516819c254e0a44cfaa3a120 (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2016-02-19T13:16:22Z (GMT) No. of bitstreams: 1
DISSERTAÇÃO_AlgorismosExatosHeurísticos.pdf: 1324128 bytes, checksum: d6be4d92516819c254e0a44cfaa3a120 (MD5) / Made available in DSpace on 2016-02-19T13:16:22Z (GMT). No. of bitstreams: 1
DISSERTAÇÃO_AlgorismosExatosHeurísticos.pdf: 1324128 bytes, checksum: d6be4d92516819c254e0a44cfaa3a120 (MD5)
Previous issue date: 2015 / O presente trabalho trata do projeto, implementação e avaliação de algoritmos exatos
e heur ísticos, sequenciais e paralelos, para a resolu c~ao do problema da enumera c~ao de
cliques com peso acima de um limiar (PECPL). Esse problema considera um grafo com
vertices ponderados, onde o objetivo e encontrar todos os cliques maximais com peso
acima de um limiar. Os algoritmos estudados neste trabalho são aplicados na separa ção
de cortes no contexto de Programa ção Inteira. Encontrar todos os cliques acima de
um dado peso e equivalente ao problema de encontrar todas as desigualdades violadas
de clique. Foram desenvolvidas adapta ções em algoritmos conhecidos na literatura,
para a resolução do problema. Para o algoritmo de Bron-Kerbosch, uma adapta c~ao
foi realizada para resolver o PECPL. Al em disso, v arias melhorias foram propostas a
m de melhorar a efi ciência na resolu ção das instâncias do problema. Foram propostas
uma versão iterativa do algoritmo, originalmente recursivo, e uma versão paralela. O
algoritmo de Ostergard e a heur stica busca tabu com multi-vizinhanças tamb ém foram
implementados e modi ficados para re
etir o problema abordado no presente trabalho.
Por m, a metaheur stica Simulated Annealing foi proposta e desenvolvida utilizando-se
das mesmas estruturas de vizinhan ca utilizadas na heur stica busca tabu com multivizinhanças. A diferen ça das duas t ecnicas est a na estrat égia de resolu ção do problema:
enquanto a primeira utiliza-se do conceito de lista tabu, a ultima simula o processo
de recozimento de metais. Nos experimentos computacionais, foram utilizadas 7292
instâncias, oriundas de quatro conjuntos referentes a separa ção de cortes em problemas
formulados por meio do uso de programa c~ao inteira. Os experimentos foram conduzidos
em duas partes: em um primeiro momento, as instâncias foram utilizadas para resolu ção
do PECPL. Posteriormente, o foco foi a resolu ção do problema do clique de peso m áximo
(PCPM). Quanto a resolu c~ao do PECPL, os resultados obtidos comprovam a efi ciência
do algoritmo de Bron-Kerbosch, quando comparado aos demais algoritmos, ao encontrar
a solu ção ótima para todas as instâncias e em um tempo consideravelmente menor do que as outras t ecnicas. Quando a an alise dos resultados foi direcionada a resolu c~ao do
PCPM, todas as t écnicas implementadas obtiveram bons resultados, com destaque para a
heur stica busca tabu com multi-vizinhan cas, a qual resolveu todas as instâncias de forma
ótima, com o menor tempo computacional em rela c~ao as demais abordagens. Como
trabalhos futuros, são sugeridos a ado c~ao de operadores l ogicos para a representa c~ao do
grafo no algoritmo de Bron-Kerbosch, a melhoria da vers~ao paralela do algoritmo e o
estudo do projeto das metaheurí sticas Simulated Annealing e busca tabu. __________________________________________________________________________________ / ABSTRACT : This work deals with the design, implementation and evaluation of exact and heuristic
algorithms, sequential and parallel to the resolution of clique enumeration problem
with weight above a threshold (PECPL). This problem considers a graph with weighted
vertices, where the goal is to nd all maximal cliques with weight above a threshold.
The algorithms studied in this work are applied in the separation cuts in the context of
Integer Programming. Find all clique above a certain weight is equivalent to the problem
of nding all the inequalities violated clique. Adaptations were developed algorithms
known in the literature, to solve the problem. For the Bron-Kerbosch algorithm, an
adaptation was made to solve the PECPL. In addition, several improvements were proposed
in order to improve e ciency in the resolution of problem instances. It has been
proposed an iterative version of the algorithm, recursive originally, and a parallel version.
The Ostergard algorithm and multi-neighborhoods tabu search heuristic were also
implemented and modi ed to re
ect the problem addressed in this paper. Finally, the
Simulated Annealing metaheuristic was proposed and developed using the same neighborhood
structures used in multi-neighborhoods tabu search heuristic. The di erence
of the two techniques is in solving strategy problem: while the rst is used the concept
of tabu list, the last simulates the process of annealing of metals. In the computational
experiments, we used 7292 instances, belonging to four sets related to the separation
cuts in problems formulated by using integer programming. The experiments were conducted
in two parts: at rst, the instances were used for solving the PECPL. Later,
the focus was on resolving the maximum weight clique problem (PCPM). As for the
resolution of the PECPL, the results prove the e ciency of Bron-Kerbosch algorithm,
when compared to other algorithms to nd the optimal solution for all instances and in
a considerably shorter time than the other techniques. When analyzing the results was
directed to resolving the PCPM, all techniques implemented performed well, particularly
the multi-neighborhoods tabu search heuristic, which solved all instances optimally with less computational time compared to other approaches. As future work, it is suggested
the adoption of logical operators for the representation of the graph in Bron-Kerbosch
algorithm, improved parallel version of the algorithm and the study design of simulated
annealing and tabu search metaheuristics.
| Identifer | oai:union.ndltd.org:IBICT/oai:localhost:123456789/6311 |
| Date | January 2015 |
| Creators | Vilas Boas, Matheus Guedes |
| Contributors | Santos, Haroldo Gambini |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFOP, instname:Universidade Federal de Ouro Preto, instacron:UFOP |
| Rights | Autorização concedida ao Repositório Institucional da UFOP pelo autor, 16/12/2016, com as seguintes condições: disponível sob Licença Creative Commons 4.0, que permite copiar, distribuir e transmitir o trabalho, desde que seja citado o autor e licenciante. Não permite o uso para fins comerciais nem a adaptação desta., info:eu-repo/semantics/openAccess |
Page generated in 0.0025 seconds