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

Carla T. L. S. Ghidini, Aurelio R. L. Oliveira, Antonio C. Moretti

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.


Palavras-chave


Problema de Corte Unidimensional; Geração de Colunas; Método de Pontos Interiores

Texto completo:

PDF

Referências


Campello, B. C., Ayres, A. O. C., Oliveira, W. A. e Ghidini, C. T. L. S. Uma nova abordagemheur ́ıstica para determinar os padr ̃oes de corte no problema de corte de estoque,ProceedingSeries of the Brazilian Society of Computational and Applied Mathematics, volume 5, 2017.

Chen, C. S., Hart, S. M. and Tham, W. M. A simulated annealing heuristic for the one-dimensional cutting stock problem,European Journal of Operations Research, 93:522–535,1996.

Degraeve, Z. and Peeters, M. Optimal integer solutions to industrial cuttingstock problems:Part 2, benchmark results,INFORMS Journal on Computing, 15(1):58–81, 2003.

Gau, T. and W ̈ascher, G. CUTGEN1: A problem generator for the standard one-dimensionalcutting stock problem,European Journal of Operational Research, 84:572–579, 1995.

Gilmore, P. C. and Gomory, R. E. A Linear Programming Approach to the Cutting-StockProblem,Operations Research, 9(6):849–859, 1961.

Hoto, R., Maculan, N., Marques, F. e Arenales, M. Um problema de corte com padr ̃oescompartimentados,Pesquisa Operacional, 23(1):169–187, 2003.

Poldi, K. C. e Arenales, M. N. Heur ́ısticas para o problema de corte de estoque unidimensionalinteiro,Pesquisa Operacional, 26(3):473–492, 2006.

Suliman, S. M. A. Pattern generating procedure for the cutting stock problem,InternationalJournal of Production Economics, 74:293–301, 2001.

W ̈ascher, G. and Gau, T. Heuristics for the integer one-dimensional cutting stock problem: Acomputational study,Operations-Research-Spektrum, 18(3):131–144, 1996.

S.J. Wright,Primal-Dual Interior Point Methods. SIAM Publications, Philadelphia, 1996.




DOI: https://doi.org/10.5540/03.2021.008.01.0501

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato