DIFFERENT TRANSFORMATIONS FOR SOLVING NONCONVEX TRIM-LOSS PROBLEMS BYMINLP

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 t hat the cost function, including the trim loss as well as the costs fo r 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, t hereafter, be solved as mixed-integer linear programming problems or c onvex mixed-integer non-linear programming problems. The linear and co nvex formulations are attractive from a formal point of view, since gl obal optimal solutions to the originally non-convex problem can be obt ained. However, as the examples considered will show, the numerical ef ficiency of the solutions from the different transformed formulations varies considerably. An example based on a trim optimization problem e ncountered daily at a Finnish paper converting mill is, finally, prese nted in order to demonstrate differences in the numerical solutions. ( C) 1998 Elsevier Science B.V.