Linear models for 1-group two-dimensional guillotine cutting problems.

In this study we present integer linear and non-linear models to generate 1-group constrained and unconstrained two-dimensional guillotine cutting patterns, including exact and non-exact cases. These patterns appear in different cutting processes as, for example, in the furniture industry. The models are useful for research and development of more effective solution methods, exploring particular structures, model decomposition, model relaxations, etc. They are also helpful for the performance evaluation of heuristic methods, since they allow (at least for problems of moderate size) an estimation of the optimality gap of heuristic solutions. To demonstrate the effectiveness of the proposed models, we compare them with models of the literature by solving a number of examples randomly generated and an actual example derived from a furniture company. Such results were produced using a well-known commercial software (the modelling language GAMS and the solver CPLEX) and they show that the computational efforts required to solve the models can be very different. [ABSTRACT FROM AUTHOR]