Duality gap estimation of linear equality constrained binary quadratic programming

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

8 Scopus Citations
View graph of relations


  • Xiaojin Zheng
  • Xiaoling Sun
  • Duan Li
  • Yong Xia


Original languageEnglish
Pages (from-to)864-880
Journal / PublicationMathematics of Operations Research
Issue number4
Online published1 Nov 2010
Publication statusPublished - Nov 2010
Externally publishedYes


We investigate in this paper the Lagrangian duality properties of linear equality constrained binary quadratic programming. We derive an underestimation of the duality gap between the primal problem and its Lagrangian dual or SDP relaxation, using the distance from the set of binary integer points to certain affine subspace, while the computation of this distance can be achieved by the cell enumeration of hyperplane arrangement. Alternative Lagrangian dual schemes via the exact penalty and the squared norm constraint reformulations are also discussed.

Research Area(s)

  • Binary quadratic optimization, Cell enumeration, Duality gap, Lagrangian dual, Linear equality constraints, SDP relaxation