Improved estimation of duality gap in binary quadratic programming using a weighted distance measure

Yong Xia; Ruey-Lin Sheu; Xiaoling Sun; Duan Li

doi:10.1016/j.ejor.2011.10.034

Author(s)

Yong Xia
Ruey-Lin Sheu
Xiaoling Sun
Duan Li

Detail(s)

Original language	English
Pages (from-to)	351-357
Journal / Publication	European Journal of Operational Research
Volume	218
Issue number	2
Online published	9 Nov 2011
Publication status	Published - 16 Apr 2012
Externally published	Yes

Link(s)

DOI	DOI https://doi.org/10.1016/j.ejor.2011.10.034 Final Published version
	Check@CityULib
Link to Scopus	https://www.scopus.com/record/display.uri?eid=2-s2.0-84855655691&origin=recordpage
Permanent Link	https://scholars.cityu.edu.hk/en/publications/publication(4a92993d-c3d4-47f9-b604-2d9a6088dbde).html

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.

Research Area(s)

Cell enumeration and hyperplane arrangement, Lagrangian duality gap, Quadratic binary programming, Semidefinite relaxation, Weighted distance measure

Citation Format(s)

[ RIS ] [ BibTeX ]

Improved estimation of duality gap in binary quadratic programming using a weighted distance measure. / Xia, Yong; Sheu, Ruey-Lin; Sun, Xiaoling et al.
In: European Journal of Operational Research, Vol. 218, No. 2, 16.04.2012, p. 351-357.

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

Xia, Y, Sheu, R-L, Sun, X & Li, D 2012, 'Improved estimation of duality gap in binary quadratic programming using a weighted distance measure', European Journal of Operational Research, vol. 218, no. 2, pp. 351-357. https://doi.org/10.1016/j.ejor.2011.10.034

Xia, Y., Sheu, R-L., Sun, X., & Li, D. (2012). Improved estimation of duality gap in binary quadratic programming using a weighted distance measure. European Journal of Operational Research, 218(2), 351-357. Advance online publication. https://doi.org/10.1016/j.ejor.2011.10.034

Xia Y, Sheu R-L, Sun X, Li D. Improved estimation of duality gap in binary quadratic programming using a weighted distance measure. European Journal of Operational Research. 2012 Apr 16;218(2):351-357. Epub 2011 Nov 9. doi: 10.1016/j.ejor.2011.10.034

Xia, Yong ; Sheu, Ruey-Lin ; Sun, Xiaoling et al. / Improved estimation of duality gap in binary quadratic programming using a weighted distance measure. In: European Journal of Operational Research. 2012 ; Vol. 218, No. 2. pp. 351-357.