Duality Gap Estimation of Linear Equality Constrained Binary Quadratic Programming

• 成果类型: Article
• 署名作者: Zheng, Xiaojin; Sun, Xiaoling; Li, Duan; Xia, Yong
• 署名单位: Fudan University; Chinese University of Hong Kong; Beihang University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1100.0472
• 发表日期: 2010
• 页码: 864-880
• 关键词: semidefinite relaxation; cut

摘要

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.