Separable Relaxation for Nonconvex Quadratic Integer Programming: Integer Diagonalization Approach

摘要

We present in this paper an integer diagonalization approach for deriving new lower bounds for general quadratic integer programming problems. More specifically, we introduce a semiunimodular transformation in order to diagonalize a symmetric matrix and preserve integral property of the feasible set at the same time. Via the semiunimodular transformation, the resulting separable quadratic integer program is a relaxation of the nonseparable quadratic integer program. We further define the integer diagonalization dual problem to identify the best semiunimodular transformation and analyze some basic properties of the set of semiunimodular transformations for a rational symmetric matrix. In particular, we present a complete characterization of the set of all semiunimodular transformations for a nonsingular 2 × 2 symmetric matrix. We finally discuss Lagrangian relaxation and convex relaxation schemes for the resulting separable quadratic integer programming problem and compare the tightness of different relaxation schemes.