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

• Processo: 07/01746-5
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de setembro de 2007
• Data de Término da vigência: 28 de fevereiro de 2009
• Área de 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
• Palavra(s)-Chave do Pesquisador: Geração de Colunas | problemas de corte | programação inteira | otimização

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 (ICMC/SB) São Carlos.