Kesavan, Padmanaban; Allgor, Russell J.; Gatzke, Edward P.; Barton, Paul I. Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs. (English) Zbl 1136.90024 Math. Program. 100, No. 3 (A), 517-535 (2004). The authors develop an exact and an approximation algorithm for a separable mixed-integer program (P) of the form \[ \begin{aligned}\min_{x,y}\qquad f(x)+c'y&\\ g_1(x)+B_1y&\leq 0\\ g_2(x)+B_2y&\leq 0\\ Ax&\leq b\\ y &\in \{0,1\}^n\end{aligned} \] where \(g_1(x)\) is a continuous, but nonconvex function and \(g_2(x)\) is convex on the nonempty compact set \(X:=\{x\mid Ax\leq b\}\). The authors replace \(f\) and \(g_1\) on \(X\) by convex, continuous differentiable underestimators \(L_1\) and \(L_2\). As in a generalized Benders’ scheme alternately a mixed-integer LP (master problem) involving linearizations of \(L_1\) and \(L_2\) and two nonlinear programming problems are solved. This yields a sequence of nondecreasing lower bounds and upper bounds which converge in a finite number of steps. Several refinements of the algorithms for an efficient implementation are discussed. Moreover, numerical results on a number of test problems are presented. Reviewer: Rainer E. Burkard (Graz) Cited in 31 Documents MSC: 90C11 Mixed integer programming 90C26 Nonconvex programming, global optimization 90C30 Nonlinear programming Keywords:mixed-integer nonlinear programming; nonconvex programming; decomposition algorithm Software:alphaBB; DAEPACK; MINOS PDFBibTeX XMLCite \textit{P. Kesavan} et al., Math. Program. 100, No. 3 (A), 517--535 (2004; Zbl 1136.90024) Full Text: DOI