Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach

Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach

0.00 Avg rating0 Votes
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: , ,
Keywords: programming: quadratic
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.