TY - JOUR
T1 - Improved estimation of duality gap in binary quadratic programming using a weighted distance measure
AU - Xia, Yong
AU - Sheu, Ruey Lin
AU - Sun, Xiaoling
AU - Li, Duan
N1 - Funding Information:
This research was supported by Research Grants Council of Hong Kong under Grant 414610 , by National Natural Science Foundation of China under Grants 10971034 , 70832002 and 11001006 , by NSFC/RGC Joint Research Project under grant 71061160506 , by Taiwan NSC 98-2115-M-006-010-MY2 , by the fund of State Key Laboratory of Software Development Environment under Grant SKLSDE-2011ZX-15 , and by fundamental research funds for the Central Universities under Grant YWF-11-03-Q-051 .
Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
PY - 2012/4/16
Y1 - 2012/4/16
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84855655691&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84855655691&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2011.10.034
DO - 10.1016/j.ejor.2011.10.034
M3 - Article
AN - SCOPUS:84855655691
SN - 0377-2217
VL - 218
SP - 351
EP - 357
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 2
ER -