Integração de heurísticas lagrangeanas com algoritmos exatos para a otimização de particionamento de conjuntos

• Ano de defesa: 2007
• Autor(a) principal: Alves, Alexsandro de Oliveira
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: 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
• Link de acesso: http://www.repositorio.ufc.br/handle/riufc/16938

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.