Geração de Colunas em Problemas de Otimização Combinatória

O estudo e desenvolvimento de técnicas eficientes para Otimização Combinatória, tem tornado possível a obtenção da solução ótima de uma abrangente quantidade e tamanhos de problemas de Programação Linear Inteira (PLI). Várias pesquisas têm focalizado seus esforços na obtenção de relaxações mais justas para esses problemas, no sentido de que elas forneçam uma solução mais próxima da solução ótima. Decomposições e reformulações de problemas de PLI têm sido intensamente desenvolvidas com esse propósito. Em geral, a decomposição e a reformulação de problemas de PLI resultam em um número excessivamente grande de variáveis (colunas). Este trabalho discute essas técnicas em um método exato de enumeração implícita, usualmente denominado branch-and-price, que combina apropriadamente geração de colunas em problemas de programação linear com branch-and-bound, já clássico em problemas de PLI. Muitos problemas de otimização combinatória podem ser formulados como problemas de particionamento. Além disso, grande parte dos algoritmos de geração de colunas para problemas de PLI têm sido desenvolvidos para formulações baseadas nesse problema. Assim, o principal resultado deste trabalho consiste na implementação de um esquema de branching proposto para o caso particular do problema de particionamento com variáveis binárias. Os resultados se referem à implementação do branchand-price para o problema de bin packing. Algumas alternativas que têm influência significativa no desempenho do algoritmo também são discutidas.