Different transformations for solving non-convex trim-loss problems by MINLP. (English) Zbl 0955.90095

Summary: 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 nonlinear 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.


90C11 Mixed integer programming
90C10 Integer programming
90C30 Nonlinear programming
90C05 Linear programming
Full Text: DOI


[1] Crowder, H.; Johnson, E.L.; Padberg, M., Solving large-scale zero-one linear programming problems, Operations research, 31, 803-834, (1983) · Zbl 0576.90065
[2] Coverdale, I.; Wharton, F., An improved heuristic procedure for a nonlinear cutting stock problem, Management science, 23, 78-86, (1976)
[3] Duran, M.A.; Grossmann, I.E., An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Mathematical programming, 36, 307-339, (1986) · Zbl 0619.90052
[4] Floudas, C.A., ()
[5] Geoffrion, A.M., Generalized benders decomposition, Journal of optimization theory and applications, 10, 4, 237-260, (1972) · Zbl 0229.90024
[6] Haessler, R.W., A heuristic programming solution to a nonlinear cutting stock problem, Management science B, 17, 793-802, (1971) · Zbl 0219.90021
[7] Haessler, R.W., Controlling cutting pattern changes in one-dimensional trim problems, Operations research, 23, 3, 483-493, (1973) · Zbl 0301.90030
[8] Harjunkoski, I.; Westerlund, T.; Isaksson, J.; Skrifvars, H., Different formulations for solving trim loss problems in a paper converting mill with ILP, Computers and chemical engineering, 20, Suppl. A, S121-S126, (1996)
[9] Hinxman, A.I., The trim-loss and assortment problems: a survey, European journal of operational research, 9, 849-859, (1980) · Zbl 0442.90072
[10] Land, A.H.; Doig, A., An automatic method of solving discrete programming problems, Ecometrica, 28, 497-520, (1960) · Zbl 0101.37004
[11] Skrifvars, H.; Harjunkoski, I.; Westerlund, T.; Kravanja, Z.; Pörn, R., Comparison of different MINLP methods applied on some chemical engineering problems, Computers and chemical engineering, 20, Suppl. A, S333-S338, (1996)
[12] Van Roy, T.J.; Wolsey, L.A., Solving mixed 0-1 programs by automatic reformulation, Operations research, 35, 45-57, (1987) · Zbl 0614.90082
[13] Westerlund, T.; Pettersson, F.; Grossmann, I.E., Optimization of pump configurations as a MINLP problem, Computers and chemical engineering, 18, 9, 845-858, (1994)
[14] Westerlund, T.; Pettersson, F., An extended cutting plane method for solving convex MINLP problems, Computers and chemical engineering suppl, 19, 131-136, (1995)
[15] Westerlund, T.; Isaksson, J.; Harjunkoski, I., Solving a production optimization problem in a paper converting mill with MILP, Computers and chemical engineering, 21, (1997)
[16] Viswanathan, J.; Grossmann, I.E., DICOPT++: a program for mixed integer non-linear optimization, ()
[17] Wäscher, G., An LP-based approach to cutting stock problems with multiple objectives, European journal of operational research, 440, 175-184, (1990) · Zbl 0684.90081
[18] Yuan, X.; Pibouleanu, D.S., Experiments in process synthesis via mixed-integer programming, Chemical engineering processes, 25, 99-116, (1989)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.