Tighter relaxations for the cutting stock problem

In the cutting stock problem (CSP) a given order for smaller pieces has to be cut from larger stock material in such a way that the number of stock material needed is minimal. Based on the classical integer linear programming model the common solution technique consists of solving the corresponding continuous relaxation problem followed by several heuristics which construct integer solutions. In many cases an optimal solution can be obtained quickly in this way. But for instances which do not possess the integer round-up property the optimality of the solution obtained cannot be verified by means of the linear programming bound. In order to overcome this non-satisfactory situation, two tighter relaxations of the CSP are proposed, and results of theoretical and numerical investigations are presented.