a Faculty of Science, Technical University Dresden, Zellescher Weg 12-14, Dresden 01062, Germany b Department of Mathematics and Computer Science, Technical University Bergakademie Freiberg, Akademiestr. 6, Freiberg 09596, Germany
Abstract:
Its linear relaxation is often solved instead of the one-dimensional cutting stock problem (1CSP). This causes a difference between the optimal objective function values of the original problem and its relaxation, called a gap. The size of this gap is considered in this paper with the aim to formulate principles for the construction of instances of the 1CSP with large gaps. These principles are complemented by examples for such instances.