Busca avançada
Ano de início
Entree

Geração de colunas para o problemas de corte em duas fases

Processo: 07/01746-5
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de setembro de 2007
Vigência (Término): 28 de fevereiro de 2009
Área do conhecimento:Engenharias - Engenharia de Produção - Pesquisa Operacional
Pesquisador responsável:Marcos Nereu Arenales
Beneficiário:Aline Aparecida de Souza Leão
Instituição-sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
Assunto(s):Problemas de corte e empacotamento   Branch-and-price   Métodos de geração de colunas   Algoritmos

Resumo

Problemas de Corte são amplamente estudados na literatura com aplicações bem sucedidas. A maioria dos trabalhos encontrados na literatura tratam do problema de corte com uma única fase, ou seja, os objetos maiores passam somente por um fase de corte. Problemas de Corte em Múltiplas Fases (MultCut Problem) possuem pouca bibliografia, porém, são de grande importância estratégica. Para estes problemas os objetos maiores são cortados em objetos intermediários, os quais são cortados para montar os itens finais. Problemas de corte podem ser modelados por um PLI, no qual é possível empregar a Técnica de Geração de Colunas de Gilmore e Gomory (1961, 1963, 1965). Recentemente têm sido desenvolvidas técnicas especializadas de Geração de Colunas, como a geração simultânea de linhas e colunas para a resolução de problemas com múltiplos estágios. Uma estratégia frequentemente utilizada ao empregar a Geração de Colunas na resolução de um PLI consiste em relaxar as variáveis inteiras e, utilizar alguma heurística de arredondamento para obter uma solução inteira viável. O desenvolvimento de heurísticas de arredondamento está fortemente ligado ao estudo da propriedade de arredondamento para cima e sua generalização. Neste projeto pretendemos escrever a decomposição de dantzig-wolfe para o problema de cortes duas-fases para futuramente desenvolver um algoritmo de partição e avaliação, também conhecido como branch-and-price para obter soluções inteiras do problema de corte em duas fases. Um algoritmo branch-and-price consiste da elaboração de uma árvore onde em cada nó é resolvida uma Geração de Colunas, visando obter uma solução ótima inteira do PLI sendo, portanto, alvo de pesquisas que tem contribuído para o estado da arte. Deste modo, decompor o problema, permitirá a determinação de regras de ramificação de um algoritmo do tipo branch-and-price, além de um estudo teórico deste tipo de abordagem, o que justifica um mestrado neste tema. (AU)

Publicações acadêmicas
(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)
LEÃO, Aline Aparecida de Souza. Geração de colunas para problemas de corte em duas fases. 2009. Dissertação de Mestrado - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação São Carlos.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.