Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs
type: Item
instance of: scholarly article
title: Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs
zbMATH Open document ID: 1136.90024
author: Padmanaban Kesavan
author: Russell J. Allgor
author: Edward P. Gatzke
author: Paul I. Barton
published in: Mathematical Programming. Series A. Series B
publication date: 2004-10-28T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C11
Mathematics Subject Classification ID: 90C26
Mathematics Subject Classification ID: 90C30
zbMATH DE Number: 2111484
zbMATH Keywords: mixed-integer nonlinear programming
zbMATH Keywords: nonconvex programming
zbMATH Keywords: decomposition algorithm
reviewed by: Rainer E. Burkard
cites work: alphaBB
describes a project that uses: alphaBB
describes a project that uses: DAEPACK
describes a project that uses: MINOS
MaRDI profile type: Publication
full work available at URL: s10107-004-0503-1
OpenAlex ID: W2090633148
DOI: 10.1007/S10107-004-0503-1
description: scientific article; zbMATH DE number 2111484