Some proximity and sensitivity results in quadratic integer programming

We show that for any optimal solution {Mathematical expression} for a given separable quadratic integer programming problem there exist an optimal solution {Mathematical expression} for its continuous relaxation such that {Mathematical expression} where n is the number of variables and Δ(A) is the largest absolute subdeterminant of the integer constraint matrix A. Also for any feasible solution z, which is not optimal for the separable quadratic integer programming problem, there exists a feasible solution {Mathematical expression} having greater objective function value and with {Mathematical expression}. We further prove, under some additional assumptions, that the distance between a pair of optimal solutions to an integer quadratic programming problem with right hand side vectors b and b′, respectively, depends linearly on {norm of matrix}b-b′{norm of matrix}₁. Finally the validity of all the results for nonseparable mixed-integer quadratic programs is established. The proximity results obtained in this paper are extensions of some of the results described in Cook et al. (1986) for linear integer programming.