ИСТИНА

We consider the well-known cutting stock problem (CSP). The gap of a CSP instance is the difference between its optimal function value and optimal value of its continuous relaxation. For most instances of CSP the gap is less than 1 and the maximal known gap was found by Rietz and Dempe[11]. Their method is based on constructing instances with large gaps from so-called sensitive instances with some additional constraints, which are hard to fulfill. We adapt our method presented in[15] to search for sensitive instances with required properties and construct a CSP instance with gap. We also present several instances with large gaps much smaller than previously known.