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.I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
