Separable Relaxation for Nonconvex Quadratic Integer Programming : Integer Diagonalization Approach

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

6 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)463-489
Journal / PublicationJournal of Optimization Theory and Applications
Volume146
Issue number2
Online published11 May 2010
Publication statusPublished - Aug 2010
Externally publishedYes

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.

Research Area(s)

  • Convex relaxation, Lagrangian relaxation, Quadratic integer programming, Semiunimodular congruence transformation, Separable relaxation