ИСТИНА

We consider the well-known cutting stock problem (CSP). An instance of CSP possesses IRUP (the integer round up property) if difference (the gap) between its optimal function value and optimal value of its continuous relaxation is less than 1. If the gap is 1 or greater, then an instance is non-IRUP. Constructing non-IRUP instances is very hard and a question about how large the gap can be is an open theoretical problem. Aim of our research is to find non-IRUP instances with minimal capacity. We have found a non-IRUP instance with integer sizes of items having capacity L=16, while a previously known instance of such kind had capacity L = 18. We prove that all instances with capacity L \le 10 have IRUP.