Cutting stock problems have been deeply investigated in the last 30 years due to their wide range of applications as well as to their nice structure. The 1 dimensional problem consists of cutting out of the minimum number of standard length pieces, the required number of pieces for each demand length. The so called MultiCut model has been the reference ILP formulation since its proposal, due to the small duality gap, but the problem structure has neven been further exploited to devise alternative ways of solving the linear relaxation of such model. In this paper we propose a new formulation of the linear relaxation in terms of min cost hyperflows on a particular class of hypergraphs, whose properties allow to taylor and improve the performance of an algorithm recently proposed for general min cost hyperflows. Computational results on benchmark instances obtained by the CUTGEN generator experimentally show the our algorithm outperforms state of the art solvers for almost all instances.

The one-dimensional cutting stock problem: a linear programming algorithm based on hyperflows

NONATO, Maddalena;
1998

Abstract

Cutting stock problems have been deeply investigated in the last 30 years due to their wide range of applications as well as to their nice structure. The 1 dimensional problem consists of cutting out of the minimum number of standard length pieces, the required number of pieces for each demand length. The so called MultiCut model has been the reference ILP formulation since its proposal, due to the small duality gap, but the problem structure has neven been further exploited to devise alternative ways of solving the linear relaxation of such model. In this paper we propose a new formulation of the linear relaxation in terms of min cost hyperflows on a particular class of hypergraphs, whose properties allow to taylor and improve the performance of an algorithm recently proposed for general min cost hyperflows. Computational results on benchmark instances obtained by the CUTGEN generator experimentally show the our algorithm outperforms state of the art solvers for almost all instances.
1998
Cutting stock; min cost hyperflow
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in SFERA 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/11392/1862123
 Attenzione

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

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