Improved estimation of duality gap in binary quadratic programming using a weighted distance measure

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

2 Scopus Citations
View graph of relations


  • Yong Xia
  • Ruey-Lin Sheu
  • Xiaoling Sun
  • Duan Li


Original languageEnglish
Pages (from-to)351-357
Journal / PublicationEuropean Journal of Operational Research
Issue number2
Online published9 Nov 2011
Publication statusPublished - 16 Apr 2012
Externally publishedYes


We present in this paper an improved estimation of duality gap between binary quadratic program and its Lagrangian dual. More specifically, we obtain this improved estimation using a weighted distance measure between the binary set and certain affine subspace. We show that the optimal weights can be computed by solving a semidefinite programming problem. We further establish a necessary and sufficient condition under which the weighted distance measure gives a strictly tighter estimation of the duality gap than the existing estimations.

Research Area(s)

  • Cell enumeration and hyperplane arrangement, Lagrangian duality gap, Quadratic binary programming, Semidefinite relaxation, Weighted distance measure