Uma modificação na técnica de geração colunas para o problema de corte unidimensional

Resumo

O problema corte unidimensional já foi e continua sendo bastante estudado devido à sua ampla aplicação, principalmente, no setor industrial. Este problema, classificado como NP-difícil, pode ser representado matematicamente por um modelo de programação linear inteira, o qual, geralmente, é resolvido por meio de métodos heurísticos. Um método heurístico muito conhecido e utilizado para a sua resolução é o método simplex com geração de colunas. Este método considera, inicialmente, um conjunto limitado de colunas, que representam os padrões de corte e a cada iteração um novo padrão de corte é gerado resolvendo um problema da mochila, cujos coeficientes de função objetivo são as variáveis duais do problema de corte relaxado (sem a restrição de integralidade das variáveis). Neste trabalho, propomos utilizar o centro analítico da face ótima do politopo dual ao invés das variáveis duais do método simplex para construir o problema da mochila e com isso acelerar a convergência do método. Os experimentos computacionais realizados mostraram bons resultados para essa abordagem, especialmente quando o problema primai é altamente degenerado.