Different transformations for solving non-convex trim-loss problems by mixed integer nonlinear programming

In the present paper trim-loss problems, often named the cutting stock problem, connected to the paper industry are considered. The problem is to cut out a set of product paper rolls from raw paper rolls such that the cost function, including the trim loss as well as the costs for the over production, is minimized. The problem is non-convex due to certain bilinear constraints. The problem can, however, be transformed into linear or convex form. The resulting transformed problems can, thereafter, be solved as mixed-integer linear programming problems or convex mixed-integer non-linear programming problems. The linear and convex formulations are attractive from a formal point of view, since global optimal solutions to the originally non-convex problem can be obtained. However, as the examples considered will show, the numerical efficiency of the solutions from the different transformed formulations varies considerably. An example based on a trim optimization problem encountered daily at a Finnish paper converting mill is, finally, presented in order to demonstrate differences in the numerical solutions.