Article ID: | iaor20106175 |
Volume: | 146 |
Issue: | 2 |
Start Page Number: | 463 |
End Page Number: | 489 |
Publication Date: | Aug 2010 |
Journal: | Journal of Optimization Theory and Applications |
Authors: | Li D, Sun X L, Zheng X J |
Keywords: | programming: quadratic |
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.