|
|||||
|
|
Improved estimation of duality gap in binary quadratic programming using a weighted distance measure |
|
| Authors: | Yong Xia Xiaoling Sun |
| Institution: | a State Key Laboratory of Software Development Environment, LMIB of the Ministry of Education, School of Mathematics and System Sciences, Beihang University, Beijing 100191, PR China b Department of Mathematics, National Cheng Kung University, Taiwan c Department of Management Science, School of Management, Fudan University, Shanghai 200433, PR China d Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong |
| Abstract: | 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. |
| Keywords: | Quadratic binary programming Lagrangian duality gap Semidefinite relaxation Weighted distance measure Cell enumeration and hyperplane arrangement |
| 本文献已被 ScienceDirect 等数据库收录！ | |