Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs

TitleOuter approximation algorithms for separable nonconvex mixed-integer nonlinear programs
Publication TypeJournal Article
Year of Publication2004
AuthorsKesavan P, Allgor RJ, Gatzke EP, Barton PI
JournalMathematical Programming
KeywordsDecomposition algorithms, Global solution, Mixed-integer nonconvex nonlinear programming

A rigorous decomposition approach to solve separable mixed-integer nonlinear programs where the participating functions are nonconvex is presented. The proposed algorithms consist of solving an alternating sequence of Relaxed Master Problems (mixed-integer linear program) and two nonlinear programming problems ({NLPs}). A sequence of valid nondecreasing lower bounds and upper bounds is generated by the algorithms which converge in a finite number of iterations. A Primal Bounding Problem is introduced, which is a convex {NLP} solved at each iteration to derive valid outer approximations of the nonconvex functions in the continuous space. Two decomposition algorithms are presented in this work. On finite termination, the first yields the global solution to the original nonconvex {MINLP} and the second finds a rigorous bound to the global solution. Convergence and optimality properties, and refinement of the algorithms for efficient implementation are presented. Finally, numerical results are compared with currently available algorithms for example problems, illuminating the potential benefits of the proposed algorithm.