Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/275736
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: Relaxações Lagrangianas e planos de corte faciais na resolução de problemas de particionamento de conjuntos
Title Alternative: Lagrangian relaxations and cutting planes in solving set partitioning problemas
Author: Braga, Andrei de Almeida Sampaio, 1986-
Advisor: Souza, Cid Carvalho de, 1963-
Abstract: Resumo: O problema de particionamento de conjuntos (SPP, do inglês set partitioning problem) é considerado um dos problemas de otimização combinatória com mais vasta gama de aplicações. Para solucioná-lo, utilizam-se comumente métodos tradicionais para a resolução de problemas NP - Difíceis. Nesta dissertação, estuda-se o uso da combinação de relaxação Lagrangiana com planos de corte. Relaxação Lagrangiana é uma técnica que tem sido usada com bastante sucesso para atacar vários problemas NP-Difíceis. Os algoritmos relax-and-cut, em especial, onde se adicionam dinamicamente planos de corte a relaxações Lagrangianas, têm ganhado bastante destaque nas últimas décadas. Em [15], Cavalcante et al. aplicam um algoritmo relax-and-cut ao SPP e obtém ótimos resultados. No entanto, tal algoritmo, bem como implementações em geral da citada combinação, são ainda passíveis de refinamentos e extensões. O estudo proposto aqui é realizado por meio das seguintes extensões do referido algoritmo: a implementação de uma partida quente para o multiplicador de uma inequação adicionada; a incorporação do algoritmo a uma enumeração, gerando, assim, um branch-and-cut baseado em relaxação Lagrangiana para o SPP; a implementação do citado branch-and-cut com o emprego de relaxações alternativas e a implementação de uma versão distribuída do algoritmo

Abstract: The set partitioning problem (SPP) is considered one of the combinatorial optimization problems with the widest range of applications. To solve the SPP, one commonly uses traditional methods for NP-Hard problem solving. In this dissertation, we study the use of the combination of Lagrangean relaxation with cutting planes. Lagrangean relaxation is a technique that has been used quite successfully to tackle several NP-Hard problems. In particular, relax-and-cut algorithms, in which cutting planes are added dynamically to Lagrangean relaxations, have gained much importance in the last decades. In [15], Cavalcante et al. applied a relax-and-cut algorithm to the SPP and obtained promising results. However, that algorithm, as well as implementations of the mentioned combination in general, are still subject to refinements and extensions. The study proposed here is carried out through the following extensions of that algorithm: the implementation of a warm start to the multiplier of an added inequality; the incorporation of the algorithm to an enumeration, thus generating a Lagrangean relaxation based branch-and-cut for the SPP; the implementation of that branch-and-cut with the use of alternative relaxations and the implementation of a distributed version of the algorithm
Subject: Otimização combinatória
Programação inteira
Algoritmos
Particionamento de conjuntos (Matemática)
Language: Português
Editor: [s.n.]
Citation: BRAGA, Andrei de Almeida Sampaio. Relaxações Lagrangianas e planos de corte faciais na resolução de problemas de particionamento de conjuntos. 2011. 115 p. Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/275736>. Acesso em: 19 ago. 2018.
Date Issue: 2011
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Braga_AndreideAlmeidaSampaio_M.pdf1.04 MBAdobe PDFView/Open


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