×

Global optimization of mixed-integer nonlinear (polynomial) programming problems: The Bernstein polynomial approach. (English) Zbl 1236.90084

Summary: In this paper, we propose an algorithm for constrained global optimization of mixed-integer nonlinear programming (MINLP) problems. The proposed algorithm uses the Bernstein polynomial form in a branch-and-bound framework. Ingredients such as continuous relaxation, branching for integer decision variables, and fathoming for each subproblem in the branch-and-bound tree are used. The performance of the proposed algorithm is tested and compared with several state-of-the-art MINLP solvers, on two sets of test problems. The results of the tests show the superiority of the proposed algorithm over the state-of-the-art solvers in terms of the chosen performance metrics.

MSC:

90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
65G30 Interval and finite arithmetic
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Floudas CA (1995) Nonlinear and mixed-integer optimization: fundamentals and applications. Oxford University Press, New York · Zbl 0886.90106
[2] Duran MA, Grossmann IE (1986) An outer approximation algorithm for a class of mixed-integer nonlinear programs. Math Program 36(3): 307–339 · Zbl 0619.90052 · doi:10.1007/BF02592064
[3] Fletcher R, Leyffer S (1994) Solving mixed-integer programs by outer approximation. Math Program 66(1-3): 327–349 · Zbl 0833.90088 · doi:10.1007/BF01581153
[4] Geoffrion AM (1972) A generalized Benders decomposition. J Optim Theory Appl 10(4): 237–260 · Zbl 0229.90024 · doi:10.1007/BF00934810
[5] Gupta OK, Ravindran A (1985) Branch and bound experiments in convex nonlinear integer programming. Manag Sci 31(12): 1533–1546 · Zbl 0591.90065 · doi:10.1287/mnsc.31.12.1533
[6] Quesada I, Grossmann IE (1992) An LP/NLP based branch and bound algorithm for convex MINLP optimization problems. Comput Chem Eng 16(10–11): 937–947 · doi:10.1016/0098-1354(92)80028-8
[7] Westerlund T, Pettersson F (1995) A extended cutting plane method for solving convex MINLP problems. Comput Chem Eng 19: 131–136 · doi:10.1016/0098-1354(95)87027-X
[8] GAMS Development Corp (2009) GAMS–the solver manuals. Washington, DC
[9] Leyffer S (1999) User manual for MINLP_BB. University of Dundee numerical analysis report NA/XXX
[10] Bonami P, Biegler LT, Conn A, Cornuéjols G, Grossmann IE, Laird C, Lee J, Lodi A, Margot F, Sawaya N, Wächter A (2008) An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optim 5(2): 186–204 · Zbl 1151.90028 · doi:10.1016/j.disopt.2006.10.011
[11] SCICON Ltd (1989) SCICONIC user guide version 1.40. Milton Keynes, UK
[12] Nowak I (2005) Relaxation and decomposition methods for mixed-integer nonlinear programming. Birkhäuser Verlag, Berlin · Zbl 1089.90039
[13] Vecchietti A, Grossmann IE (1997) LOGMIP: a disjunctive 0-1 nonlinear optimizer for process system models. Comput Chem Eng 21: S427–S432
[14] Lindo systems Inc (2009) Lindo API 6.0 · Zbl 1177.90325
[15] Belotti P, Lee J, Liberti L, Margot F, Wächter A (2009) Branching and bounds tightening techniques for non-convex MINLP. Optim Methods Softw 24(4-5): 597–634 · Zbl 1179.90237 · doi:10.1080/10556780903087124
[16] Tawarmalani M, Sahinidis NV (2002) Convexification and global optimization in continuous and mixed-integer nonlinear programming: theory, algorithms, software, and applications (nonconvex optimization and its applications). Kluwer, Dordrecht · Zbl 1031.90022
[17] Nataraj PSV, Kotecha K (2002) An algorithm for global optimization using Taylor-Bernstein form as inclusion function. J Glob Optim 24(4): 417–436 · Zbl 1046.90065 · doi:10.1023/A:1021296315884
[18] Nataraj PSV, Kotecha K (2004) Global optimization with higher order inclusion function forms. Part 1: a combined Taylor-Bernstein form. Reliab Comput 10(1): 27–44 · Zbl 1038.65052 · doi:10.1023/B:REOM.0000003995.08805.2a
[19] Nataraj PSV, Arounassalame M (2007) A new subdivision algorithm for the Bernstein polynomial approach to global optimization. Int J Autom Comput 4(4): 342–352 · doi:10.1007/s11633-007-0342-7
[20] Nataraj PSV, Arounassalame M (2009) An algorithm for constrained global optimization of multivariate polynomials using the Bernstein form and John optimality conditions. Opsearch 46(2): 133–152 · Zbl 1192.90146 · doi:10.1007/s12597-009-0009-y
[21] Ray S, Nataraj PSV (2009) An efficient algorithm for range computation of polynomials using the Bernstein form. J Glob Optim 45(3): 403–426 · Zbl 1191.90046 · doi:10.1007/s10898-008-9382-y
[22] MINLP Library. http://www.gamsworld.org/minlp/minlplib/minlpstat.htm . Accessed 20 March 2010
[23] Zhu W (2005) A provable better branch and bound method for a nonconvex integer quadratic programming problem. J Comput Syst Sci 70(1): 107–117 · Zbl 1079.90167 · doi:10.1016/j.jcss.2004.07.002
[24] Lebbah Y, Michel C, Rueher M (2007) An efficient and safe framework for solving optimization problems. J Comput Appl Math 199(2): 372–377 · Zbl 1108.65065 · doi:10.1016/j.cam.2005.08.037
[25] Ray S (2007) A new approach to range computation of polynomial problems using the Bernstein form. PhD thesis, Indian Institute of Technology Bombay, India
[26] Garloff J (1985) Convergent bounds for range of multivariate polynomials. In: Nickel K (ed) Interval mathematics. Lecturer notes in computer science, vol 212. Springer, Berlin, pp 37–56
[27] Sànchez-Reyes J (2003) Algebraic manipulation in the Bernstein form made simple via convolutions. Computer-Aided Des 35(10): 959–967 · Zbl 1206.68375 · doi:10.1016/S0010-4485(03)00021-6
[28] Garczarczyk ZA (2002) Parallel schemes of computation for Bernstein coefficients and their application. In: Proceedings of the international conference on parallel computing in electrical engineering, pp 334–337, Warsaw, Poland
[29] Smith AP (2009) Fast construction of constant bound functions for sparse polynomials. J Glob Optim 43(2–3): 445–458 · Zbl 1168.90011 · doi:10.1007/s10898-007-9195-4
[30] Garloff J (1993) The Bernstein algorithm. Interval Comput 6(2): 154–168 · Zbl 0829.65017
[31] Ratschek H, Rokne J (1988) New computer methods for global optimization. Ellis Horwood, Chichester · Zbl 0648.65049
[32] Goux JP, Leyffer S (2002) Solving large MINLPs on computational grids. Optim Eng 3(3): 327–346 · Zbl 1035.90049 · doi:10.1023/A:1021047328089
[33] Linderoth JT, Savelsbergh MWP (1999) A computational study of search strategies for mixed integer programming. INFORMS J Comput 11(2): 173–187 · Zbl 1040.90535 · doi:10.1287/ijoc.11.2.173
[34] Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper Res Lett 33(1): 42–54 · Zbl 1076.90037 · doi:10.1016/j.orl.2004.04.002
[35] NEOS server for optimization. http://www.neos-server.org/neos/solvers/index.html . Accessed 20 March 2010
[36] Kuipers K (2009) Branch-and-bound solver for mixed-integer nonlinear optimization problems. MATLAB Central File Exchange. Retrieved 18 Dec 2009
[37] The Mathworks Inc (2005) MATLAB version 7.1 (R14)
[38] Moore RE (1979) Methods and applications of interval analysis. SIAM, Philadelphia · Zbl 0417.65022
[39] Stahl V (1995) Interval methods for bounding the range of polynomials and solving systems of nonlinear equations. PhD thesis, Johannes Kepler University, Linz
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.