A simple OPT+1OPT+1 algorithm for cutting stock under the modified integer round-up property assumption

We present a simple algorithm for the cutting stock problem with objects of a constant number d   of different sizes. Our algorithm produces solutions of value at most OPT+1OPT+1 in time dO(d)(log7n+s3.5), where OPT is the value of an optimum solution, n is the number of objects, and s is the total number of bits needed to encode the object sizes. This algorithm works under the assumption that the modified integer round-up property of Scheithauer and Terno for the cutting stock problem holds.

Research highlights► We present a simple algorithm for cutting stock with a constant number of sizes. ► Our algorithm produces solutions of value at most OPT+1OPT+1, where OPT is the optimum. ► The algorithm is faster than previous algorithms for the problem. ► The algorithm makes the assumption that the modified integer round-up property holds.