Global optimization of a quadratic function subject to a bounded mixed integer constraint set (Q2640438)

This paper deals with the NP-hard problem of finding a global solution to a mixed integer nonconvex quadratic program. A branch and bound algorithm is presented which requires the solution of linear programming subproblems at each node. The method is based on underestimation of the objective function and relaxation of the integer restriction. Two piecewise affine underestimating functions are developed for the function \(x^ tQx+c^ tx\) over a rectangular set \(\ell \leq x\leq L\). Noting that \(x^ ty=x^ tQx+c^ tx\) for \(y=Qx+c\), bounds \(m\leq y\leq M\) are given by \(m_ i=\min \{Q_ ix+c_ i:\ell \leq x\leq L\}\) and \(M_ i=\max \{Q_ ix+c_ i:\ell \leq x\leq L\}\), where \(Q_ i\) denotes the ith row of Q. Taking the convex envelope of \(x^ ty\) over \(\ell \leq x\leq L\), \(m\leq y\leq M\), and projecting gives an affine underestimate for \(x^ tQx+c^ tx\). Alternatively, substituting \(y_ i=Q_ ix+c_ i\) into the expression for the convex envelope yields a piecewise affine and convex underestimate. For the pure 0-1 integer case, the latter underestimate reduces to a reformulation of a quadratic binary program due to \textit{F. Glover} [Management Sci. 22 (1975), 455-460 (1976; Zbl 0318.90044)]. Overestimating functions based on concave envelopes are also derived. These are useful in establishing error bounds on the approximations and thereby ensuring finite convergence for a given tolerance.