Abstract
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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Floudas CA (1995) Nonlinear and mixed-integer optimization: fundamentals and applications. Oxford University Press, New York
Duran MA, Grossmann IE (1986) An outer approximation algorithm for a class of mixed-integer nonlinear programs. Math Program 36(3): 307–339
Fletcher R, Leyffer S (1994) Solving mixed-integer programs by outer approximation. Math Program 66(1-3): 327–349
Geoffrion AM (1972) A generalized Benders decomposition. J Optim Theory Appl 10(4): 237–260
Gupta OK, Ravindran A (1985) Branch and bound experiments in convex nonlinear integer programming. Manag Sci 31(12): 1533–1546
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
Westerlund T, Pettersson F (1995) A extended cutting plane method for solving convex MINLP problems. Comput Chem Eng 19: 131–136
GAMS Development Corp (2009) GAMS—the solver manuals. Washington, DC
Leyffer S (1999) User manual for MINLP_BB. University of Dundee numerical analysis report NA/XXX
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
SCICON Ltd (1989) SCICONIC user guide version 1.40. Milton Keynes, UK
Nowak I (2005) Relaxation and decomposition methods for mixed-integer nonlinear programming. Birkhäuser Verlag, Berlin
Vecchietti A, Grossmann IE (1997) LOGMIP: a disjunctive 0-1 nonlinear optimizer for process system models. Comput Chem Eng 21: S427–S432
Lindo systems Inc (2009) Lindo API 6.0
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
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
Nataraj PSV, Kotecha K (2002) An algorithm for global optimization using Taylor-Bernstein form as inclusion function. J Glob Optim 24(4): 417–436
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
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
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
Ray S, Nataraj PSV (2009) An efficient algorithm for range computation of polynomials using the Bernstein form. J Glob Optim 45(3): 403–426
MINLP Library. http://www.gamsworld.org/minlp/minlplib/minlpstat.htm. Accessed 20 March 2010
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
Lebbah Y, Michel C, Rueher M (2007) An efficient and safe framework for solving optimization problems. J Comput Appl Math 199(2): 372–377
Ray S (2007) A new approach to range computation of polynomial problems using the Bernstein form. PhD thesis, Indian Institute of Technology Bombay, India
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
Sànchez-Reyes J (2003) Algebraic manipulation in the Bernstein form made simple via convolutions. Computer-Aided Des 35(10): 959–967
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
Smith AP (2009) Fast construction of constant bound functions for sparse polynomials. J Glob Optim 43(2–3): 445–458
Garloff J (1993) The Bernstein algorithm. Interval Comput 6(2): 154–168
Ratschek H, Rokne J (1988) New computer methods for global optimization. Ellis Horwood, Chichester
Goux JP, Leyffer S (2002) Solving large MINLPs on computational grids. Optim Eng 3(3): 327–346
Linderoth JT, Savelsbergh MWP (1999) A computational study of search strategies for mixed integer programming. INFORMS J Comput 11(2): 173–187
Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper Res Lett 33(1): 42–54
NEOS server for optimization. http://www.neos-server.org/neos/solvers/index.html. Accessed 20 March 2010
Kuipers K (2009) Branch-and-bound solver for mixed-integer nonlinear optimization problems. MATLAB Central File Exchange. Retrieved 18 Dec 2009
The Mathworks Inc (2005) MATLAB version 7.1 (R14)
Moore RE (1979) Methods and applications of interval analysis. SIAM, Philadelphia
Stahl V (1995) Interval methods for bounding the range of polynomials and solving systems of nonlinear equations. PhD thesis, Johannes Kepler University, Linz
Author information
Authors and Affiliations
Corresponding author
Additional information
The authors have presented the results of this paper during the SCAN 2010 conference in Lyon, September 2010.
Rights and permissions
About this article
Cite this article
Patil, B.V., Nataraj, P.S.V. & Bhartiya, S. Global optimization of mixed-integer nonlinear (polynomial) programming problems: the Bernstein polynomial approach. Computing 94, 325–343 (2012). https://doi.org/10.1007/s00607-011-0175-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00607-011-0175-7