Algoritmos exatos e heurísticos para a resolução do problema da descoberta de cliques de peso máximo.
Nenhuma Miniatura disponível
Data
2015
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
O presente trabalho trata do projeto, implementação e avaliação de algoritmos exatos
e heurísticos, sequenciais e paralelos, para a resolução do problema da enumeração de
cliques com peso acima de um limiar (PECPL). Esse problema considera um grafo com
vértices ponderados, onde o objetivo é 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 é 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ção
foi realizada para resolver o PECPL. Além disso, várias melhorias foram propostas a
fim de melhorar a eficiê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 modificados para refletir o problema abordado no presente trabalho.
Porém, a metaheurística Simulated Annealing foi proposta e desenvolvida utilizando-se
as mesmas estruturas de vizinhança utilizadas na heurística busca tabu com multivizinhanças. A diferença das duas técnicas está 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 à separação de cortes em problemas
formulados por meio do uso de programação 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 à resolução do PECPL, os resultados obtidos comprovam a eficiê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écnicas. Quando a análise dos resultados foi direcionada à resolução do
PCPM, todas as técnicas implementadas obtiveram bons resultados, com destaque para a
heurística busca tabu com multi-vizinhanças, a qual resolveu todas as instâncias de forma
ótima, com o menor tempo computacional em relação às demais abordagens. Como
trabalhos futuros, são sugeridos a adoção de operadores lógicos para a representação do
grafo no algoritmo de Bron-Kerbosch, a melhoria da versão paralela do algoritmo e o
estudo do projeto das metaheurísticas Simulated Annealing e busca tabu.
Descrição
Programa de Pós-Graduação em Ciência da Computação. Departamento de Computação, Universidade Federal de Ouro Preto.
Palavras-chave
Otimização combinatória, Algoritmos de computador, Programação heurística
Citação
VILAS BOAS, Matheus Guedes. Algoritmos exatos e heurísticos para a resolução do problema da descoberta de cliques de peso máximo. 2015. 96 f. Dissertação (Mestrado em Ciência da Computação) – Universidade Federal de Ouro Preto, Ouro Preto, 2015.