Por favor, use este identificador para citar o enlazar este ítem: http://repositorio.ufc.br/handle/riufc/16938
Tipo: Dissertação
Título : Integração de heurísticas lagrangeanas com algoritmos exatos para a otimização de particionamento de conjuntos
Título en inglés: Integration of Lagrangean heuristics with exact algorithms to otimization of the set partitioning problem
Autor : Alves, Alexsandro de Oliveira
Tutor: Andrade, Rafael Castro de
Co-asesor: Campêlo Neto, Manoel Bezerra
Palabras clave : Ciência da computação;Particionamento de conjuntos;Busca tabu;Heurísticas lagrangeanas;Método do subgradiente;Branch and bound;Set partitioning;Tabu Search;Lagrangian heuristics;Subgradient method;Branch and bound
Fecha de publicación : 2007
Citación : ALVES, Alexsandro de Oliveira. Integração de heurísticas lagrangeanas com algoritmos exatos para a otimização de particionamento de conjuntos. 2007. 49 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Ceará, Fortaleza, 2007.
Resumen en portugués brasileño: Neste trabalho avaliamos métodos heurísticos e exatos para o Problema de Particionamento de Conjuntos (PPC). Realizamos testes computacionais com heurísticas lagrangeanas baseadas em algoritmos gulosos, busca tabu e método de otimização pelo subgradiente. Os resultados obtidos, comparados com os da literatura, comprovam a eficiência de nossas heurísticas na obtenção de limites inferiores e superiores de boa qualidade, em tempo computacional razoável, para instâncias da literatura. Utilizamos um esquema de Branch and Bound para tentar resolver instâncias do PPC à otimalidade e para comprovar a qualidade dos resultados alcançados por nossas heurísticas.
Abstract: In this work we evaluate both exact and heuristic methods for the set partitioning problem (SPP). These heuristics are based on greedy algorithms, tabu search and subgradient optimization. Computational experiments performed on benchmark instances of the problem indicate that our heuristics are competitive with existing ones from the literature in obtaining both lower and upper bounds of good quality in reasonable execution time. We use a Branch and Bound algorithm that allows to prove optimality of solutions obtained by our heuristics for a large set of benchmark instances of the SPP. Thus, we show that our heuristics are efficient in obtaining feasible solutions of good quality for this problem.
URI : http://www.repositorio.ufc.br/handle/riufc/16938
Aparece en las colecciones: DCOMP - Dissertações defendidas na UFC

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
2007_dis_aoalves.pdf424,35 kBAdobe PDFVisualizar/Abrir


Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.