Relaxações Lagrangianas e planos de corte faciais na resolução de problemas de particionamento de conjuntos / Lagrangian relaxations and cutting planes in solving set partitioning problemas
AUTOR(ES)
Andrei de Almeida Sampaio Braga
FONTE
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia
DATA DE PUBLICAÇÃO
02/09/2011
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
ASSUNTO(S)
otimização combinatória programação inteira algoritmos particionamento de conjuntos (matemática) combinatorial optimization integer programming algorithms set partitioning (mathematics)
ACESSO AO ARTIGO
http://libdigi.unicamp.br/document/?code=000836507Documentos Relacionados
- A STUDY ON CUTTING PLANE AND FIXING VARIABLE TECHNIQUES APPLIED TO THE RESOLUTION OF SET PARTITIONING PROBLEMS
- Fotofisica e relaxações em siliconas
- Algorithms for classification and partitioning in graphs
- IntegraÃÃo de heurÃsticas lagrangeanas com algoritmos exatos para a otimizaÃÃo de particionamento de conjuntos
- Algoritmos para problemas de corte e empacotamento