A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem

The two-dimensional orthogonal non-guillotine cutting problem (NGCP) appears in many industries (like wood and steel industries) and consists in cutting a rectangular master surface into a number of rectangular pieces, each with a given size and value. The pieces must be cut with their edges always parallel or orthogonal to the edges of the master surface (orthogonal cuts). The objective is to maximize the total value of the pieces cut. In this paper, we propose a two-level approach for solving the NGCP, where, at the first level, we select the subset of pieces to be packed into the master surface without specifying the layout, while at a second level we check only if a feasible packing layout exists. This approach has been already proposed by Fekete and Schepers [S.P. Fekete, J. Schepers, A new exact algorithm for general orthogonal d-dimensional knapsack problems, ESA 97, Springer Lecture Notes in Computer Science 1284 (1997) 144-156; S.P. Fekete, J. Schepers, On more-dimensional packing III: Exact algorithms, Tech. Rep. 97.290, Universitat zu Koln, Germany, 2000; S.P. Fekete, J. Schepers, J.C. van der Veen, An exact algorithm for higher-dimensional orthogonal packing, Tech. Rep. Under revision on Operations Research, Braunschweig University of Technology, Germany, 2004] and Caprara and Monaci [A. Caprara, M. Monaci, On the two-dimensional knapsack problem, Operations Research Letters 32 (2004) 2-14]. We propose improved reduction tests for the NGCP and a cutting-plane approach to be used in the first level of the tree search to compute effective upper bounds. Computational tests on problems derived from the literature show the effectiveness of the proposed approach, that is able to reduce the number of nodes generated at the first level of the tree search and the number of times the existence of a feasible packing layout is tested. (C) 2006 Elsevier B.V. All rights reserved.