LAUSR

We consider the well-known one-dimensional cutting stock problem in order to find some integer instances with the minimal length L of a stock material for which the round-up property is not satisfied. The difference between the exact solution of an instance of a cutting stock problem and the solution of its linear relaxation is called the integrality gap . Some instance of a cutting problem has the integer round-up property (IRUP) if its integrality gap is less than 1. We present a new method for exhaustive search over the instances with maximal integrality gap when the values of L , the lengths of demanded pieces, and the optimal integer solution are fixed. This method allows us to prove by computing that all instances with L ≤ 15 have the round-up property. Also some instances are given with L = 16 not-possessing this property, which gives an improvement of the best known result L = 18.