Solving a two-dimensional trim-loss problem with mixed integer linear programming

In this paper a two-dimensional trim-loss problem connected to the paper-converting industry is considered. The problem is to produce a set of product paper rolls from larger raw paper rolls such that the cost for waste and the cutting time is minimized. The problem is generally non-convex due to a bilinear objective function and some bilinear constraints, which give rise to difficulties in finding efficient numerical procedures for the solution. The problem can, however, be solved as a two-step procedure, where the latter step is a mixed integer linear programming (MILP) problem. In the present formulation, both the width and length of the raw paper rolls as well as the lengths of the product paper rolls are considered variables. All feasible cutting patterns are included in the problem and global optimal cutting patterns are obtained as the solution from the corresponding MILP problem. A numerical example is included to illustrate the proposed procedure.