Modelos lineares e n o lineares inteiros para problemas da mochila bidimensional restrita a 2 estágios Linear and nonlinear integer models for constrained two-stage two-dimensional knapsack problems

Neste trabalho revemos alguns modelos lineares e n o lineares inteiros para gerar padr es de corte bidimensionais guilhotinados de 2 estágios, incluindo os casos exato e n o exato e restrito e irrestrito. Esses problemas s o casos particulares do problema da mochila bidimensional. Apresentamos também novos modelos para gerar esses padr es de corte, baseados em adapta es ou extens es de modelos para gerar padr es de corte bidimensionais restritos 1-grupo. Padr es 2 estágios aparecem em diferentes processos de corte, como, por exemplo, em indústrias de móveis e de chapas de madeira. Os modelos s o úteis para a pesquisa e o desenvolvimento de métodos de solu o mais eficientes, explorando estruturas particulares, a decomposi o do modelo, relaxa es do modelo etc. Eles também s o úteis para a avalia o do desempenho de heurísticas, já que permitem (pelo menos para problemas de tamanho moderado) uma estimativa do gap de otimalidade de solu es obtidas por heurísticas. Para ilustrar a aplica o dos modelos, analisamos os resultados de alguns experimentos computacionais com exemplos da literatura e outros gerados aleatoriamente. Os resultados foram produzidos usando um software comercial conhecido e mostram que o esfor o computacional necessário para resolver os modelos pode ser bastante diferente. In this work we review some linear and nonlinear integer models to generate two stage two-dimensional guillotine cutting patterns, including the constrained, non constrained, exact and non exact cases. These problems are particular cases of the two dimensional knapsack problems. We also present new models to generate these cutting patterns, based on adaptations and extensions of models that generate one-group constrained two dimensional cutting patterns. Two stage patterns arise in different cutting processes like, for instance, in the furniture industry and wooden hardboards. The models are useful for the research and development of more efficient methods, exploring particular structures, the model decomposition, model relaxations etc. They are also useful to evaluate the performance of heuristics, since they allow (at least for problems of moderate sizes) an estimative of the optimality gap of the solutions obtained by heuristics. To illustrate the application of the models we analyze the results of some computational experiments with instances of the literature and other generated randomly. The results were produced using a known commercial software and they show that the necessary computational effort to solve the models can be very different.