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) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2007. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T18:05:04Z No. of bitstreams: 1 2007_dis_aoalves.pdf: 434539 bytes, checksum: d7550e0ddf22c4c083e44734e59375f7 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T18:08:40Z (GMT) No. of bitstreams: 1 2007_dis_aoalves.pdf: 434539 bytes, checksum: d7550e0ddf22c4c083e44734e59375f7 (MD5) / Made available in DSpace on 2016-05-20T18:08:40Z (GMT). No. of bitstreams: 1 2007_dis_aoalves.pdf: 434539 bytes, checksum: d7550e0ddf22c4c083e44734e59375f7 (MD5) Previous issue date: 2007 / 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. / 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.