The two-dimensional orthogonal non-guillotine cutting stock problem (NGCP) appears in many industries (e.g. the wood and steel industries) and consists of 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 to the edges of the master surface (orthogonal cuts). The objective is to maximize the total value of the pieces cut. New upper bounds on the optimal solution to the NGCP are described. The new bounding procedures are obtained by different relaxations of a new mathematical formulation of the NGCP. Various procedures for strengthening the resulting upper bounds and reducing the size of the original problem are discussed. The proposed new upper bounds have been experimentally evaluated on test problems derived from the literature. Comparisons with previous bounding procedures from the literature are given. The computational results indicate that these bounds are significantly better than the bounds proposed in the literature.

### New upper bounds for the two-dimensional orthogonal non-guillotine cutting stock problem

#### Abstract

The two-dimensional orthogonal non-guillotine cutting stock problem (NGCP) appears in many industries (e.g. the wood and steel industries) and consists of 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 to the edges of the master surface (orthogonal cuts). The objective is to maximize the total value of the pieces cut. New upper bounds on the optimal solution to the NGCP are described. The new bounding procedures are obtained by different relaxations of a new mathematical formulation of the NGCP. Various procedures for strengthening the resulting upper bounds and reducing the size of the original problem are discussed. The proposed new upper bounds have been experimentally evaluated on test problems derived from the literature. Comparisons with previous bounding procedures from the literature are given. The computational results indicate that these bounds are significantly better than the bounds proposed in the literature.
##### Scheda breve Scheda completa Scheda completa (DC)
2002
Boschetti M.A.; Mingozzi A.; Hadjiconstantinou E.
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: `https://hdl.handle.net/11585/879985`
##### Attenzione

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

• ND
• 42
• ND