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

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)