LP-based method for the multi-sheet cutting stock problem

The rectangular cutting-stock problem consists in laying out a specified list of rectangular pieces on a minimum number of rectangular sheets. A pattern is a way to put some rectangles from the list on a sheet. The heuristic presented in this paper associates to each pattern a variable equal to the number of times the pattern is selected, and then tries to minimize the sum of the variables. Constraints are used to insure that all rectangles from the list are laid out. The linear relaxation of a reduced problem is considered and solved, and the result is then rounded off according to a special process. The solution can then be improved via an adapted branch and bound procedure. The heuristic is tested on a number of real problems arising in the metal industry, and evaluating using lower and upper bounds.