Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs (Q1885275)

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.