Return to search

Uma an?lise experimental de algoritmos exatos aplicados ao problema da ?rvore geradora multiobjetivo / An experimental analysis of exact algorithms applied to the multiobjective spanning tree problem

Made available in DSpace on 2014-12-17T15:48:01Z (GMT). No. of bitstreams: 1
PatriciaMLLD_DISSERT.pdf: 2062279 bytes, checksum: edf20f81d921e118846850abb8ec8a1d (MD5)
Previous issue date: 2012-03-05 / The Multiobjective Spanning Tree Problem is NP-hard and models applications in several areas. This research presents an experimental analysis of different strategies used in the literature to develop exact algorithms to solve the problem. Initially, the algorithms are classified according to the approaches used to solve the problem. Features of two or more approaches can be found in some of those algorithms. The approaches investigated here are: the two-stage method, branch-and-bound, k-best and the preference-based approach. The main contribution of this research lies in the fact that no research was presented to date reporting a systematic experimental analysis of exact algorithms for the Multiobjective Spanning Tree Problem. Therefore, this work can be a basis for other research that deal with the same problem. The computational experiments compare the performance of algorithms regarding processing time, efficiency based on the number of objectives and number of solutions found in a controlled time interval. The analysis of the algorithms was performed for known instances of the problem, as well as instances obtained from a generator commonly used in the literature / O Problema da ?rvore Geradora Multiobjetivo ? NP-?rduo e modela aplica??es em diversas ?reas. Esta pesquisa apresenta uma an?lise experimental de diferentes estrat?gias utilizadas na literatura para desenvolver algoritmos exatos para resolver o problema. Inicialmente, os algoritmos s?o classificados de acordo com as abordagens utilizadas para resolver o problema. Caracter?sticas de duas ou mais abordagens podem ser encontradas em alguns desses algoritmos. As abordagens aqui investigadas s?o: o m?todo duas fases, branch-and-bound, k-best e a abordagem baseada em prefer?ncia. A principal contribui??o deste trabalho est? no fato de que nenhuma pesquisa desenvolvida at? o momento relata uma an?lise sistem?tica experimental de algoritmos exatos para o problema da ?rvore Geradora Multiobjetivo. Portanto, este trabalho pode ser uma base para outras pesquisas que lidam com o mesmo problema. Os experimentos computacionais comparam o desempenho de algoritmos em rela??o ao tempo de processamento, ? efici?ncia com base no n?mero de objetivos e no n?mero de solu??es encontradas em um intervalo de tempo controlado. A an?lise dos algoritmos foi realizada para inst?ncias conhecidas do problema, bem como para inst?ncias obtidas a partir de um gerador bastante utilizado na literatura

Identiferoai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/18047
Date05 March 2012
CreatorsDrumond, Patricia Medyna Lauritzen de Lucena
ContributorsCPF:81652011749, http://lattes.cnpq.br/2888641121265608, Ramos, Iloneide Carlos de Oliveira, CPF:24260142453, http://lattes.cnpq.br/0613948277011672, Cruz Neto, Joao Xavier da, CPF:21810141320, http://lattes.cnpq.br/9936034232663152, Siqueira, Marcelo Ferreira, CPF:67285619434, http://lattes.cnpq.br/7340736676138238, Goldbarg, Marco C?sar, CPF:25841025953, http://lattes.cnpq.br/1371199678541174, Gouv?a, Elizabeth Ferreira
PublisherUniversidade Federal do Rio Grande do Norte, Programa de P?s-Gradua??o em Sistemas e Computa??o, UFRN, BR, Ci?ncia da Computa??o
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Formatapplication/pdf
Sourcereponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0017 seconds