Use este identificador para citar ou linkar para este item: 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 em inglês: Integration of Lagrangean heuristics with exact algorithms to otimization of the set partitioning problem
Autor(es): Alves, Alexsandro de Oliveira
Orientador: Andrade, Rafael Castro de
Coorientador: Campêlo Neto, Manoel Bezerra
Palavras-chave: 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
Data do documento: 2007
Citação: 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.
Resumo: 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 nas coleções:DCOMP - Dissertações defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2007_dis_aoalves.pdf424,35 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.