×

zbMATH — the first resource for mathematics

An improved Bernstein global optimization algorithm for MINLP problems with application in process industry. (English) Zbl 1302.90139
Summary: We present an improved Bernstein global optimization algorithm to solve polynomial mixed-integer nonlinear programming (MINLP) problems. The algorithm is of branch-and-bound type, and uses the Bernstein form of the polynomials for the global optimization. The new ingredients in the algorithm include a modified subdivision procedure, a vectorized Bernstein cut-off test and a new branching rule for the decision variables. The performance of the improved algorithm is tested and compared with earlier reported Bernstein global optimization algorithm (to solve polynomial MINLPs) and with several state-of-the-art MINLP solvers on a set of 19 test problems. The results of the tests show the superiority of the improved algorithm over the earlier reported Bernstein algorithm and the state-of-the-art solvers in terms of the chosen performance metrics. Similarly, efficacy of the improved algorithm in handling a real-world MINLP problem is brought out via a trim-loss minimization problem from the process industry.

MSC:
90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
90C90 Applications of mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T.; Koch, T.; Martin, A., Branching rules revisited, Oper. Res. Lett., 33, 42-54, (2005) · Zbl 1076.90037
[2] Androulakis, I.P.; Maranas, C.D.; Floudas, C.A., Α-BB: a global optimization method for general constrained nonconvex problems, J. Glob. Optim., 7, 337-363, (1995) · Zbl 0846.90087
[3] Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wächter, A., Branching and bounds tightening techniques for non-convex MINLP, Optim. Method Softw., 24, 597-634, (2009) · Zbl 1179.90237
[4] Bonami, P.; Biegler, L.T.; Conn, A.R.; Cornuéjols, G.; Grossmann, I.E.; Laird, C.D.; Lee, J.; Lodi, A.; Margot, F.; Sawaya, N.; Wächter, A., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim., 5, 186-204, (2008) · Zbl 1151.90028
[5] Burer, S.; Letchford, A.N., Non-convex mixed-integer nonlinear programming: a survey, Surv. Oper. Res. Manag. Sci., 17, 97-106, (2012)
[6] Bussieck, M.R.; Drud, A.S.; Meeraus, A., Minlpliba collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput., 15, 114-119, (2003) · Zbl 1238.90104
[7] Duran, M.A.; Grossmann, I.E., An outer approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program, 36, 307-339, (1986) · Zbl 0619.90052
[8] Fletcher, R.; Leyffer, S., Solving mixed-integer programs by outer approximation, Math. Program, 66, 327-349, (1994) · Zbl 0833.90088
[9] Floudas C.A.: Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications. Oxford University Press, New York (1995) · Zbl 0886.90106
[10] GAMS Development Corporation: GAMS—The Solver Manuals. GAMS Development Corporation, Washington, DC (2009) · Zbl 1179.90237
[11] Garczarczyk, Z.A.: Parallel schemes of computation for Bernstein coefficients and their application. In: Proceedings of the International Conference on Parallel Computing in Electrical Engineering, Warsaw, pp. 334-337 (2002)
[12] Garloff, J.: Convergent bounds for range of multivariate polynomials, in interval mathematics. In: Nickel, K. (ed.) Lecturer Notes in Computer Science, vol. 212. Springer, Berlin, pp. 37-56 (1985) · Zbl 1206.68375
[13] Garloff, J., The Bernstein algorithm, Interval Comput., 6, 154-168, (1993) · Zbl 0829.65017
[14] Geoffrion, A.M., A generalized benders decomposition, J. Optim. Theory Appl., 10, 237-260, (1972) · Zbl 0229.90024
[15] Goux, J.P.; Leyffer, S., Solving large MINLPs on computational grids, Optim. Eng., 3, 327-346, (2002) · Zbl 1035.90049
[16] Gropp, W., More, J.: Optimization environments and the NEOS server. In: Buhmann, M.D., Iserles, A. (eds.) Approximation Theory and Optimization. Cambridge University Press, Cambridge, pp. 167-182 (1997) · Zbl 1031.65075
[17] Gupta, O.K.; Ravindran, A., Branch and bound experiments in convex nonlinear integer programming, Manag. Sci., 31, 1533-1546, (1985) · Zbl 0591.90065
[18] Harjunkoski, I.; Westerlund, T.; Pörn, R., Numerical and environmental considerations on a complex industrial mixed integer non-linear programming (MINLP) problem, Comput. Chem. Eng., 23, 1545-1561, (1999)
[19] Harjunkoski, I.; Westerlund, T.; Pörn, R.; Skrifvars, H., Different transformations for solving non-convex trim-loss problems by MINLP, Eur. J. Oper. Res., 105, 594-603, (1998) · Zbl 0955.90095
[20] Kuipers, K.: Branch-and-bound solver for mixed-integer nonlinear optimization problems. In: MATLAB Central for File Exchange (2003) · Zbl 0619.90052
[21] Leyffer, S.: User manual for INLP_BB. In: University of Dundee Numerical Analysis Report NA/XXX (1999) · Zbl 0955.90095
[22] Linderoth, J.T.; Savelsbergh, M.W.P., A computational study of search strategies for mixed integer programming, INFORMS J. Comput., 11, 173-187, (1999) · Zbl 1040.90535
[23] LINGO User’s Manual. Lindo systems, Inc., Chicago IL (2009) · Zbl 1040.90535
[24] Mathworks: The Mathworks Inc., MATLAB version 7.1 (R14). Mathworks, Natick (2005) · Zbl 1236.90084
[25] Nataraj, P.S.V.; Arounassalame, M., A new subdivision algorithm for the Bernstein polynomial approach to global optimization, IJAC, 4, 342-352, (2007)
[26] Nataraj, P.S.V.; Arounassalame, M., An algorithm for constrained global optimization of multivariate polynomials using the Bernstein form and John optimality conditions, Opsearch, 46, 133-152, (2009) · Zbl 1192.90146
[27] Nataraj, P.S.V.; Arounassalame, M., Constrained global optimization of multivariate polynomials using Bernstein branch and prune algorithm, J. Global Optim., 49, 185-212, (2011) · Zbl 1209.90294
[28] Nowak I.: Relaxation and Decomposition Methods for Mixed-Integer Nonlinear Programming. Birkhäuser Verlag, Berlin (2005) · Zbl 1089.90039
[29] Patil, B.V.; Nataraj, P.S.V.; Bhatiya, S., Global optimization of mixed-integer nonlinear (polynomial) programming problems: the Bernstein polynomial approach, Computing, 94, 325-343, (2012) · Zbl 1236.90084
[30] Quesada, I.; Grossmann, I.E., An LP/NLP based branch and bound algorithm for convex MINLP optimization problems, Comput. Chem. Eng., 16, 937-947, (1992)
[31] Ray, S.; Nataraj, P.S.V., An efficient algorithm for range computation of polynomials using the Bernstein form, J. Global Optim., 45, 403-426, (2009) · Zbl 1191.90046
[32] Sanchez-Reyes, J., Algebraic manipulation in the Bernstein form made simple via convolutions, Comput. Aided Des., 35, 959-967, (2003) · Zbl 1206.68375
[33] Schluter, M., Gerdts, M., Ruckmann, J.J.: MIDACO: New Global Optimization Software for MINLP. http://www.midaco-solver.com/about.html (2012). Accessed 20 Dec 2012 · Zbl 1260.90149
[34] SCICON Ltd.: SCICONIC User Guide Version 1.40. Milton Keynes, UK (1989)
[35] Smith, A.P., Fast construction of constant bound functions for sparse polynomials, J. Global Optim., 43, 445-458, (2009) · Zbl 1168.90011
[36] Stahl, V.: Interval Methods for Bounding the Range of Polynomials and Solving Systems of Nonlinear Equations. PhD thesis, Johannes Kepler University, Linz (1995) · Zbl 0833.90088
[37] Tawarmalani M., Sahinidis N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming : Theory, Algorithms, Software and Applications. Kluwer Academic Publishers, Dordrecht (2002) · Zbl 1031.90022
[38] Telesa, J.P.; Castro, P.M.; Matos, H.A., Univariate parameterization for global optimization of mixed-integer polynomial problems, Eur. J. Oper. Res., 229, 613-625, (2013) · Zbl 1317.90213
[39] Vecchietti, A.; Grossmann, I.E., LOGMIP: a disjunctive 0-1 nonlinear optimizer for process system models, Comput. Chem. Eng., 21, s427-s432, (1997)
[40] Westerlund, T.; Pettersson, F., A extended cutting plane method for solving convex MINLP problems, Comput. Chem. Eng., 19, 131-136, (1995)
[41] Zettler, M.; Garloff, J., Robustness analysis of polynomials with polynomial parameter dependency using Bernstein expansion, IEEE Trans. Autom. Control, 43, 425-431, (1998) · Zbl 0906.93046
[42] Zhu, W., A provable better branch and bound method for a nonconvex integer quadratic programming problem, J. Comput. Syst. Sci., 70, 107-117, (2005) · Zbl 1079.90167
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.