In the present paper, trim loss problems connected to the paper-converting industry are analyzed and solved. The objective is to produce a set of paper rolls from storage rolls such that a cost function including the minimization of the trim loss as well as the time for cutting is considered. The problem is a non-convex integer non-linear programming (INLP) problem, due to its bilinear constraints. The problem can, however, be written in an expanded linear form and can, thus, be solved as an integer linear programming (ILP) or a mixed integer linear programming (MILP) problem. The linear formulation is attractive from the point of view of formality. One drawback of linear formulations is the increased number of variables and constraints they give rise to. It is, though, of interest to compare different ways of describing the problem as an ILP/MILP problem. There has previously been some academic interest in solving trim loss problems as linear programming problems. In this paper, we will present a general INLP formulation, some ways to formulate and solve it as an ILP or MILP problem and compare the efficiency of these different approaches. The examples considered are taken from real daily trim optimization problems encountered at a Finnish paper-converting mill with a capacity of 100,000 tons/year.