Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/16938
Title in Portuguese: Integração de heurísticas lagrangeanas com algoritmos exatos para a otimização de particionamento de conjuntos
Title: Integration of Lagrangean heuristics with exact algorithms to otimization of the set partitioning problem
Author: Alves, Alexsandro de Oliveira
Advisor(s): Andrade, Rafael Castro de
Co-advisor(s): Campelo Neto, Manoel Bezerra
Keywords: 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
Issue Date: 2007
Citation: 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.
Abstract in Portuguese: 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
metadata.dc.type: Dissertation
Appears in Collections:DCOMP - Dissertações defendidas na UFC

Files in This Item:
File Description SizeFormat 
2007_dis_aoalves.pdf424,35 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.