×

Mixed-integer linear methods for layout-optimization of screening systems in recovered paper production. (English) Zbl 1364.90227

Summary: The industrial treatment of waste paper in order to regain valuable fibers from which recovered paper can be produced, involves several steps of preparation. One important step is the separation of stickies that are normally attached to the paper. If not properly separated, remaining stickies reduce the quality of the recovered paper or even disrupt the production process. For the mechanical separation process of fibers from stickies a separator screen is used. This machine has one input feed and two output streams, called the accept and the reject. In the accept the fibers are concentrated, whereas the reject has a higher concentration of stickies. The machine can be controlled by setting its reject rate. But even when the reject rate is set properly, after just a single screening step, the accept still has too many stickies, or the reject too many fibers. To get a better separation, several separators have to be assembled into a network. From a mathematical point of view this problem can be seen as a multi-commodity network flow design problem with a nonlinear, controllable distribution function at each node. We present a nonlinear mixed-integer programming model for the simultaneous selection of the network’s topology and the optimal setting of each separator. Numerical results are obtained via different types of linearization of the nonlinearities and the use of mixed-integer linear solvers, and compared with state-of-the-art global optimization software.

MSC:

90C11 Mixed integer programming
90C90 Applications of mathematical programming
90B10 Deterministic network models in operations research
Full Text: DOI

References:

[1] Achterberg T (2009) Scip: solving constraint integer programs. Math Program Comput 1(1):1-41. http://mpc.zib.de/index.php/MPC/article/view/4. Accessed 13 Feb 2014 · Zbl 1171.90476
[2] Ahmed S, Vielma JP, Nemhauser G (2009) Mixed-integer models for nonseparable piecewise linear optimization: unifying framework and extensions. Oper Res 58(2):303-315 · Zbl 1226.90046
[3] Almin KE, Steenberg B (1954) The capacity problem in single series screen cascades—studies in screening theory ii. Sven Papperstidning 57(2):37-40
[4] Arrow KJ, Enthoven AC (1961) Quasi-concave programming. Econometrica 29(4):779-800 · Zbl 0104.14302 · doi:10.2307/1911819
[5] Ballerstein M, Kienle A, Kunde C, Weismantel R, Michaels D Towards global optimization of combined distillation-crystallization processes for the separation of closely boiling mixtures. In: Pistikopoulos EN, Georgiadis MC, Kokossis AC (eds) 21th European Symposium on Computer Aided Process Engineering—ESCAPE 21. Elsevier, Amsterdam, 2011, pp 552-556 · Zbl 1364.74074
[6] Ballerstein M, Michaels D, Seidel-Morgenstern A, Weismantel R (2010) A theoretical study of continuous counter-current chromatography for adsorption isotherms with inflection points. Comp Chem Eng 34(4):447-459 · doi:10.1016/j.compchemeng.2009.10.001
[7] Ballerstein M, Michaels D, Vigerske S (2013) Linear underestimators for bivariate functions with a fixed convexity behavoir. Technical report, ZIB Report 13-02, Konrad-Zuse-Zentrum für Informationstechnik Berlin (Germany). (revision in preparation)
[8] Bartholdi JJ, Goldsman P (2001) Continuous spatial indexing of surfaces. Part 1: standard triangulations. Technical report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia · Zbl 1179.90237
[9] Bauer MH, Stichlmair J (1996) Struktursynthese und Optimierung nicht-idealer Rektifizierprozesse. Chemie Ingenieur Technik 68:911-916 · doi:10.1002/cite.330680803
[10] Belotti P, Lee J, Liberti L, Margot F, Wächter A (2009) Branching and bounds tightening techniques for non-convex MINLP. Optim Methods Softw (Special Issue: GLOBAL OPTIMIZATION) 24(4-5):597-634 · Zbl 1179.90237 · doi:10.1080/10556780903087124
[11] Benson HP (2004) On the construction of convex and concave envelope formulas for bilinear and fractional functions on quadrilaterals. Comput Optim Appl 27:5-22 · Zbl 1045.90068 · doi:10.1023/B:COAP.0000004976.52180.7f
[12] Bergamini ML, Aguirre P, Grossmann IE (2005) Logic-based outer approximation for globally optimal synthesis of process networks. Comput Chem Eng 29:1914-1933 · doi:10.1016/j.compchemeng.2005.04.003
[13] Bergamini ML, Grossmann IE, Scenna N, Aguirre P (2008) An improved piecewise outer-approximation algorithm for the global optimization of MINLP models involving concave and bilinear terms. Comput Chem Eng 32:477-493 · doi:10.1016/j.compchemeng.2007.03.011
[14] Bixby RE (2002) Solving real-world linear programs: a decade and more of progress. Oper Res 50(1):1-13 · Zbl 1163.90643 · doi:10.1287/opre.50.1.3.17780
[15] Cameron SH (1966) Piece-wise linear approximations. Technical report, IIT Research Institute
[16] Cantoni A (1971) Optimal curve fitting with piecewise-linear functions. IEEE Trans Comput C 20:59-67 · Zbl 0213.43504 · doi:10.1109/T-C.1971.223082
[17] Dantzig G, Johnson S, White W (1959) A linear programming approach to the chemical equilibrium problem. Manag Sci 5:38-43 · Zbl 0995.90596 · doi:10.1287/mnsc.5.1.38
[18] Dantzig GB (1963) Linear programming and extensions. Princeton University Press, London · Zbl 0108.33103
[19] de Boor C (2001) A practical guide to splines. Springer, Berlin · Zbl 0987.65015
[20] Der Verband Deutscher Papierfabriken e.V. (VDP) (2007) Papier Kompass. http://bio-based.eu/news/media/news-images/20070724-11/Kompassdeutsch.pdf. Accessed 13 Feb 2014 · Zbl 0960.90065
[21] Duran MA, Grossmann IE (1986) An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math Program 36:307-339 · Zbl 0619.90052 · doi:10.1007/BF02592064
[22] Ehrgott M (2000) Multicriteria optimization. Springer, Berlin · Zbl 0956.90039 · doi:10.1007/978-3-662-22199-0
[23] Floudas CA (1987) Separation synthesis of multicomponent feed streams into multicomponent product streams. AIChE J 33:540-550 · doi:10.1002/aic.690330403
[24] Floudas CA (1995) Nonlinear and mixed-integer optimization. Fundamentals and applications. Oxford University Press, New York · Zbl 0886.90106
[25] Franke M, Górak A, Strube J (2004) Auslegung und Optimierung von hybriden Trennverfahren. Chemie Ingenieur Technik 76:199-210 · doi:10.1002/cite.200406150
[26] Franke MB, Nowotny N, Ndocko EN, Górak A, Strube J (2008) Design and optimization of a hybrid distillation/melt-crystallization process. AIChE J 54(11):2925-2942 · doi:10.1002/aic.11605
[27] Frey T, Brusis D, Stichlmair J, Bauer MH, Glanz S (2000) Systematische Prozesssynthese mit Hilfe mathematischer Methoden. Chemie Ingenieur Technik 72:812-821 · doi:10.1002/1522-2640(200008)72:8<813::AID-CITE813>3.0.CO;2-3
[28] Friedler F, Tarjan K, Huang YW, Fan LT (1993) Graph-theoretic approach to process synthesis: polynomial algorithm for maximal structure generation. Comput Chem Eng 17:929-942 · doi:10.1016/0098-1354(93)80074-W
[29] Fügenschuh A, Herty M, Klar A, Martin A (2006) Combinatorial and continuous models for the optimization of traffic flows on networks. SIAM J Optim 16:1155 - 1176 · Zbl 1131.90015 · doi:10.1137/040605503
[30] Galor O (2006) Discrete dynamical systems. Springer, New York
[31] Gangadwala J, Kienle A, Haus U-U, Michaels D, Weismantel R (2006) Global bounds on optimal solutions for the production of 2,3-dimethylbutene-1. Ind Eng Chem Res 45(7):2261-2271 · doi:10.1021/ie050584j
[32] Gavrilovic MM (1975) Optimal approximation of convex curves by functions which are piecewise linear. J of Math Anal Appl 52:260-282 · Zbl 0317.65005 · doi:10.1016/0022-247X(75)90095-5
[33] Geißler B, Martin A, Morsi A, Schewe L (2010) Using piecewise linear functions for solving MINLPs. In: IMA Volume on MINLP. Springer, Berlin · Zbl 1242.90132
[34] Geoffrion AM (1972) Generalized benders decomposition. J Optim Theory Appl 10(4):237-260 · Zbl 0229.90024 · doi:10.1007/BF00934810
[35] Grossmann IE (1985) Mixed-integer programming approache for the synthesis of integrated process flowsheets. Comput Chem Eng 9:463-482 · doi:10.1016/0098-1354(85)80023-5
[36] Grossmann IE, Aguirre PA, Barttfeld M (2005) Optimal synthesis of complex distillation columns using rigorous models. Comput Chem Eng 29:1203-1215 · doi:10.1016/j.compchemeng.2005.02.030
[37] Gürth DA (2007) Approximation von bivariaten Funktionen mittels Orthogonalitätsrelationen für lineare Splines. Master’s thesis, TU Darmstadt, Fachbereich Mathematik
[38] Hamman B, Chen J (1994) Data point selection for piecewise linear curve approximation. Comput Aided Geom Des 11(3):289-301 · Zbl 0804.65019 · doi:10.1016/0167-8396(94)90004-3
[39] Haus U-U, Michaels D, Seidel-Morgenstern A, Weismantel R (2007) A method to evaluate the feasibility of TMB chromatography for reduced efficiency and purity requirements based on discrete optimization. Comput Chem Eng 31(11):1525-1534 · doi:10.1016/j.compchemeng.2007.01.001
[40] Heckl I, Kovacs Z, Friedler F, Fan LT (2003) Super-structure generation for separation network synthesis involving different separation methods. Chem Eng Trans 3:1209-1214
[41] IBM ILOG CPLEX (2010) http://www.ibm.com/software/integration/optimization/cplex/. Accessed 13 Feb 2014 · Zbl 1268.90052
[42] Imai H, Iri M (1986) An optimal algorithm for approximating a piecewise linear function. J Inf Process 9:159-162 · Zbl 0631.65010
[43] Jach M, Michaels D, Weismantel R (2008) The convex envelope of (n-1)-convex functions. SIAM J Optim 19(3):1451-1466 · Zbl 1176.90467 · doi:10.1137/07069359X
[44] Johnson EL, Nemhauser GL, Savelsbergh MWP (2000) Progress in linear programming-based algorithms for integer programming: an exposition. INFORMS J Comput 12(1):2-23 · Zbl 1052.90048 · doi:10.1287/ijoc.12.1.2.11900
[45] Keha AB, de Farias IR, Nemhauser GL (2004) Models for representing piecewise linear cost functions. Oper Res Lett 32(1):44-48 · Zbl 1056.90107 · doi:10.1016/S0167-6377(03)00059-2
[46] Khajavirad A, Sahidinidis NV (2012) Convex envelopes of products of convex and component-wise concave functions. J Glob Optim 52:391-409 · Zbl 1268.90052 · doi:10.1007/s10898-011-9747-5
[47] Khajavirad A, Sahinidis NV (2013) Convex envelopes generated from finitely many compact convex sets. Math Program Ser A 137:371-408 · Zbl 1284.90055 · doi:10.1007/s10107-011-0496-5
[48] Koch T(2004) Rapid mathematical programming. PhD thesis, Technische Universität Berlin. ZIB-Report 04-58 · Zbl 1131.90015
[49] Kraemer K, Kossack S, Marquardt W (2009) Efficient optimization-based design of distillation processes for homogeneous azeotropic mixtures. Ind Eng Chem Res 48:6749-6764 · doi:10.1021/ie900143e
[50] Kubat J, Steenberg B (1955) Screening at low particle concentrations—studies in screening theory III. Sven Papperstidning 58(9):319-324
[51] Lee GS (1982) Piecewise linear approximation of multivariate functions. Bell Syst Tech J 61:1463-1486 · Zbl 0492.65005 · doi:10.1002/j.1538-7305.1982.tb04354.x
[52] Lee J, Wilson D (2001) Polyhedral methods for piecewise-linear functions. I: the lambda method. Discret Appl Math 108(3):269-285 · Zbl 1002.90038 · doi:10.1016/S0166-218X(00)00216-X
[53] Linderoth J (2005) A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs. Math Program 103(2, Ser. B):251-282 · Zbl 1099.90039 · doi:10.1007/s10107-005-0582-7
[54] Locatelli M (2010) Convex envelopes for quadratic and polynomial functions over polytopes. http://www.optimization-online.org/DB_FILE/2010/11/2788.pdf. Accessed 13 Feb 2014
[55] Locatelli M, Schoen F (2009) On the convex envelopes and underestimators for bivariate functions. http://www.optimization-online.org/DB_FILE/2009/11/2462.pdf. Accessed 17 Nov 2009 · Zbl 1085.90047
[56] Lowe JK (1984) Modelling with integer variables. PhD thesis, Georgia Institute of Technology · Zbl 0554.90081
[57] Manis G, Papakonstantinou G, Tsanakas P (1977) Optimal piecewise linear approximation of digitized curves. In: 13th International Conference on Digital Signal Processing Proceedings, DSP 97, Volume: 2. Dept. of Electr. & Comput. Eng., Nat. Tech. Univ. of Athens, IEEE Xplore, pp 1079-1081. doi:10.1109/ICDSP.1997.628552
[58] Markowitz H, Manne A (1957) On the solution of discrete programming-problems. Ecometrica 25:84-110 · Zbl 0078.34005 · doi:10.2307/1907744
[59] McCormick GP (1976) Computability of global solutions to factorable nonconvex programs. I: convex underestimating problems. Math Program 10:147-175 · Zbl 0349.90100 · doi:10.1007/BF01580665
[60] Meyer CA, Floudas CA (2003) Trilinear monomials with positive or negative domains: facets of the convex and concave envelopes. In: Floudas Christodoulos A, Pardalos PM (eds) Frontiers in global optimization. Kluwer Academic Publishers, Dordrecht, pp 327-352 · Zbl 1176.90469
[61] Meyer CA, Floudas CA (2004) Trilinear monomials with mixed sign domains: facets of the convex and concave envelopes. J Glob Optim 29:125-155 · Zbl 1085.90047 · doi:10.1023/B:JOGO.0000042112.72379.e6
[62] Meyer CA, Floudas CA (2005) Convex envelopes for edge-concave functions. Math Program Ser B 103:207-224 · Zbl 1099.90045 · doi:10.1007/s10107-005-0580-9
[63] Moritz S (2006) A mixed integer approach for the transient case of gas network optimization. PhD thesis, TU Darmstadt, Fachbereich Mathematik
[64] Muraki M, Hayakawa T (1984) Separation process synthesis for multicomponent products. J Chem Eng Jpn 17:533 · doi:10.1252/jcej.17.533
[65] Muraki M, Hayakawa T (1987) Multicomponent product separation synthesis with separation sharpness. J Chem Eng Jpn 20:195-198 · doi:10.1252/jcej.20.195
[66] Nath R, Motard RL (1981) Evolutionary synthesis of separation processes. AIChE J 27:578-587 · doi:10.1002/aic.690270407
[67] Nemhauser GL, Vielma JP (2008) Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. Lecture Notes in Computer Science. vol 5035, pp 199-213. Springer, New York · Zbl 1143.90384
[68] Nemhauser GL, Wolsey LA (1988) Integer and combinatorial optimization. Wiley Interscience, New York · Zbl 0652.90067
[69] Nishida N, Stephanopoulos G, Westerberg AW (1981) A review of process synthesis. AIChE J 27:321-351 · doi:10.1002/aic.690270302
[70] Ortega JM (1972) Iterative solution of nonlinear equations in several variables. Academic Press, New York
[71] Padberg M (2000) Approximating separable nonlinear functions via mixed zero-one programs. Oper Res Lett 27:1-5 · Zbl 0960.90065 · doi:10.1016/S0167-6377(00)00028-6
[72] Pozo C, Guillén-Gosálbez G, Sorribas A, Jeménez L (2011) A spatial branch-and-bound framework for the global optimization of kinetic models of metabolic networks. Ind Eng Chem Res 50:5225-5238 · doi:10.1021/ie101368k
[73] Rockafellar RT (1970) Convex analysis. Princeton Landmarks in Mathematics. Princeton University Press, Princeton · Zbl 0193.18401
[74] Rosenthal RE (1988) GAMS: A user’s guide. The Scientific Press, Redwood City
[75] Sahinidis NV, Tawarmalani M (2005) BARON 7.2.5: Global optimization of mixed-integer nonlinear programs
[76] Schönberger C (2007) Linearization methods for the optimization of screening processes in the recovered paper production. Master’s thesis, TU Darmstadt · Zbl 1273.90165
[77] Schwarz HR, Köckler N (2006) Numerische Mathematik. Teubner Verlag, Wiesbaden · Zbl 1136.65003
[78] Skiborowski M, Harwardt A, Marquardt W (2013) Conceptual design of distillation-based hybrid separation processes. Ann Rev Chem Biomol Eng 4:45-68
[79] Steenberg B (1953) Principles of screening system design—studies in screening theory I. Sven Papperstidning 56:771-778
[80] Stone H (1961) Approximation of curves by line segments. Math Comput 15:40-47 · Zbl 0097.14001 · doi:10.1090/S0025-5718-1961-0119390-6
[81] Tawarmalani M, Richard J-P, Xiong C (2013) Explicit convex and concave envelopes through polyhedral subdivisions. Math Program Ser A 138(1-2):531-578 · Zbl 1273.90165 · doi:10.1007/s10107-012-0581-4
[82] Tawarmalani M, Sahinidis NV (2001) Semidefinite relaxations of fractional programs via novel convexification techniques. J Glob Optim 20:137-158 · Zbl 1001.90064 · doi:10.1023/A:1011233805045
[83] Tawarmalani M, Sahinidis NV (2002) Convex extensions and envelopes of lower semi-continuous functions. Math Program A 93:247-263 · Zbl 1065.90062 · doi:10.1007/s10107-002-0308-z
[84] Tawarmalani M, Sahinidis NV (2004) Global optimization of mixed-integer nonlinear programs: a theoretical and computational study. Math Program 99:563-591 · Zbl 1062.90041 · doi:10.1007/s10107-003-0467-6
[85] Tawarmalani M, Sahinidis NV (2005) A polyhedral branch-and-cut approach to global optimization. Math Program 103(2, Ser. B):225-249 · Zbl 1099.90047 · doi:10.1007/s10107-005-0581-8
[86] The MathWorks. Matlab version 7.9 (R2009b), 2009
[87] Tomek I (1974) Two algorithms for piecewise-linear continuous approximation of functions of one variable. IEEE Trans Comput 23:445-448 · Zbl 0284.68078 · doi:10.1109/T-C.1974.223961
[88] Tomlin JA (1981) A suggested extension of special ordered sets to nonseparable nonconvex programming problems. In: Studies on graphs and discrete programming (Brussels, 1979), volume 11 of Ann. Discrete Math., pp 359-370. North-Holland · Zbl 0469.90068
[89] Urselmann M, Barkmann S, Sand G, Engell S (2011) Optimization-based design of reactive distillation columns using a memetic algorithm. Comput Chem Eng 35:787-805 · doi:10.1016/j.compchemeng.2011.01.038
[90] Valkama J-P (2006) Erabeitung eines Analysewerkzeugs für Altpapier verarbeitende Papierfabriken zur objektiven Bewertung der Grenzen der Stickyabtrennung durch Sortierprozesse. Abschlussbericht AiF-Projekt 18990 N. Technical report, Fachgebiet Papierfabrikation und Mechanische Verfahrenstechnik, TU Darmstadt
[91] Valkama J-P (2007) Optimisation of Low Consistency Fine Screening Processes in Recycled Paper Production, volume 1 of Fortschritt-Berichte Papiertechnik /Progress in Paper Technology 1. Shaker
[92] Vandewalle J (1975) On the calculation of the piecewise linear approximation to a discrete function. IEEE Trans Comput 24:843-846 · Zbl 0309.68041 · doi:10.1109/T-C.1975.224320
[93] Wilson DL (1998) Polyhedral methods for piecewise-linear functions. PhD thesis, University of Kentucky, Department of Mathematics
[94] Wolsey LA (1998) Integer programming. Wiley Interscience, New York · Zbl 0930.90072
[95] Wunderling R (1996) Paralleler und objektorientierter Simplex-Algorithmus. PhD thesis, Technische Universität Berlin · Zbl 0871.65048
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.