Article ID: | iaor20108772 |
Volume: | 35 |
Issue: | 4 |
Start Page Number: | 864 |
End Page Number: | 880 |
Publication Date: | Nov 2010 |
Journal: | Mathematics of Operations Research |
Authors: | Li Duan, Sun Xiaoling, Xia Yong, Zheng Xiaojin |
Keywords: | duality, Lagrangian relaxation |
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.