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.

A Cutting Plane Approach for the Two-Dimensional Orthogonal Non Guillotine Cutting Stock Problem

BALDACCI, ROBERTO;BOSCHETTI, MARCO ANTONIO
2007

Abstract

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.
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/18906
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 43
  • ???jsp.display-item.citation.isi??? 32
social impact